Bill Allombert on Sun, 08 Oct 2023 18:39:40 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: efficient foursquare() and/or threesquare1m4() functions
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: efficient foursquare() and/or threesquare1m4() functions
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Sun, 8 Oct 2023 18:38:28 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696783149; c=relaxed/relaxed; bh=xekJoIP+VHoUvtBJ+wmUI9L+DLCmKqrzGDhNEHjdvHU=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=AmriviKMieZDOswyCalx0TTviUZeXPgdvQ7pgPybQfHRGbYgz3uHV/L/LSx/QoLIVwA1F7n5nycfbU07YZoVm2e0TJsONDSrKZJtX1MhOabUeYQheu2KtxNfQuSWr5Ld1N3IWyowCScmXBV577x3FnUYgbRDP8enEo35dALT/XuMO15BbbKxGvk8IBB21BwUA+h2DTkQAIE818m3L3otm74BzNOSkxJpLcCGgCNlX3WFCXSgvamYTOhn77oN3NJS8p7RhPMKXPD+T1dSylhENfKK0FB7PVxcU35Js7O6dMzYhCqmofhDIK/4vAsm3FEJLJS2hxapq6Is53cirpwBfQMe7CGYTj00+SxDkrhpHfnBlE2NmDjwPZCFXc4fVhnnNJvZuBqKHEuBkYS7iIaJRFyCQklsEI/knmrGRAgBZ6F/Pn+y0+ddOLS9vILn1z3AmpjJgUYWQKNwWlT15RHVYfei9J2YGWuVyM/a0WvBQNoVAO+F+uJgY0svDtzdLQWEJ198Ont1oowSIUp7b3qPUvViFpYz7lhh+n0Gf13CmUXGD7d3M1npK2mYSpCDV4VtJifUDwpNDcfFl4u7wyuEnbRadKQS5urKtmCgE1YISS0nqjzw2tD/b7OmH6AzQKEoVF9Lc6KenZ/ekdeNG7RmSzskV7VFjlLNJeszg2av0SM=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696783149; cv=none; b=k297lt33f5N+m+RXWSxzYavQ/MqdeEVYERrc2zufuuJ3dHuD2+QA9m5MkrUMwMccmFD/uPooBT8JggSA0fA52ozyxzb2S88QyTYgf7Jiw9wjTqJil5dAq6xvKr6O74zYv1OzVKCAfF6femmKeKCtJiyU9Etk29XnL3RGg9EOEWU4HT4rqyWmjxr4QvNdm9F3TFaF7iCVT/RHO0fsB2xQkBuTW2hW/tuDse0KepKfoH4ugWqd63JFYj7rA5+ZYUbfO/DTXT2cFyM0ULoUL0M7U0AIOVBUsplq3SYqbOPU3x1fKLKhO2Zpz/DJWipUn32r1OAwIH2lHRnPzgOU8FOZsKNZBJSeSpvO/2I3+oxiaiOuwSV6xTVzbYE/Ae46vGcHiERDW6WZk7qfkHPVeQsBZi75v1bBCefnKFVIILZKLiRJqIopxGD/oS3alLYox9F0MhHe2Ubq/oJWOjjryAFRjixVO3HuxN2Ml6iaNqwWk12Yqyv9+II9c6QN4pyvmyrI2TQcOGOHDufg83K/vB49D4UK2aj8ScJTIEWdbaTQ4wv25OgXhw1gOnrwidoO/cVz+B/Iyd+F3BoHkB6VkxcOa2Ru9r/tghHefkuqEz8mDNLfc2hwZAFATVcgsq/7jY+uCv5VWb28D5R4sSnM/85LMB6jYLVola1tRB6FK3BSnew=
- Authentication-results: smail; arc=none
- Delivery-date: Sun, 08 Oct 2023 18:39:40 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1696783149; bh=xekJoIP+VHoUvtBJ+wmUI9L+DLCmKqrzGDhNEHjdvHU=; h=Date:From:To:Subject:References:In-Reply-To:From; b=rtgDT8BZyFnxqhOKYMWjAnuGsdGG1Fi53S+dAh0+sXZijpAQCr4m5DVxS58UVCTm0 KfyBxOSSU2HiZlL7/aqYQ4qZe9BulbELyT5DCCBExbuwGl/Xj90kNZjlTSJ+eElRjM zbEsctmOAwWZQ/HEMjWUVEgRfzdsSCxaCP6OvGbwUUGCan+GLxV1Nas6IOZyNIwO5j teV/qLzt9L5XifLVHxsYFpeim5+uzGYDEIOhcexWWKbOrVPG0XhZ0zVNvPE3WoWcga vOLUHIpaXLvT/rFzh2HaNOJnAupnt9I/6srReXjtTTUtFm+m7N8CnLwSrOJ10EPOWi iV1s+3iqjPegspTVCbMOJhHZGpAgi7jSSBiFAL4otn5eKCcvMsmrRqttCGxvnqgl4W q1G/6k1FiOXj4uYGQoShY9dpABQYlHpS6sG7+ixK0/vbloC3u7zHvyCkjx0R7KOTai RimISJHLNQEVy6iT2zANKC/mbAnQgdUmvxHo0erXWp8Wcyy2gPXqp376OwXt9+OueU uBgD0zaYjD16iuFUSJfa3a5D56MLlzI7pCK62md/nOHmKYYpgqWNviCzFbCdfRglPF pf4H+wq0PUz6mqtkXuZuZbQ2CUkn5HOlgZ3WuIG/s/uPL5cgbdEftz1Aa6FDEN1SFa 4/jNoKagwtbab6TNmHF0y8FI=
- In-reply-to: <d1c78430066dfb66eb8919b4cde59d9c@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <d1c78430066dfb66eb8919b4cde59d9c@stamm-wilbrandt.de>
On Fri, Oct 06, 2023 at 01:06:31AM +0200, hermann@stamm-wilbrandt.de wrote:
> In this posting Bill provided function "foursquare(n)":
> https://pari.math.u-bordeaux.fr/archives/pari-users-2310/msg00004.html
>
> foursquare(n) = abs(qfsolve(matdiagonal([1,1,1,1,-n]))[1..4]);
I join a script that should handle all cases.
(two/three/four squares with or without factorization, except
for two squares without factoring, which I do not know how to do.)
Cheers,
Bill
twosquares(n)=abs(qfbsolve(Qfb(1,0,1),n))
threesquares_fact(n)=abs(qfsolve(matdiagonal([1,1,1,-n]))[1..3])~
fouresquares_fact(n)=abs(qfsolve(matdiagonal([1,1,1,1,-n]))[1..4])~
isfact(n)=my(F=factor(n,2^20)[,1]);ispseudoprime(F[#F]);
threesquares(n)=
{
if(isfact(n),return(threesquares_fact(n)));
forstep(i=sqrtint(n),1,-1,
my(P=n-i^2,v = valuation(P,2), Q = P/2^v);
if(Q%4==1 && ispseudoprime(Q),return(concat(i,twosquares(P)))));
}
foursquares(n)=
{
if(isfact(n),return(foursquares_fact(n)));
forstep(i=sqrtint(n),1,-1,
my(P=n-i^2, v = valuation(P,2)\2);
if (P/4^v%8!=7,
my(F=factor(P,2^20)[,1]);
if(ispseudoprime(F[#F]),
return(concat(i,threesquares_fact(P))))));
}
test()=
{
my(P=randomprime(2^500,Mod(1,8))*randomprime(2^500,Mod(7,8)));
my(F=foursquares(P));
if (#F!=4 || norml2(F)!=P,error("foursquares",P));
my(P=randomprime(2^500,Mod(1,8))*randomprime(2^500,Mod(3,8)));
my(F=threesquares(P));
if (#F!=3 || norml2(F)!=P,error("threesquares",P));
}