Re: efficient foursquare() and/or threesquare1m4() functions

[hermann@stamm-wilbrandt.de]

On 2023-10-08 18:38, Bill Allombert wrote:
> 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.)
Hi Bill,

threesquares() sometimes produces length 1 result vector
for RSA numbers n =1 (mod 4), which are definitely not squares.

twosquares(n)=abs(qfbsolve(Qfb(1,0,1),n))
threesquares_fact(n)=abs(qfsolve(matdiagonal([1,1,1,-n]))[1..3])~
...
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)))));
}
...

So wrong result for RSA-x with x in {129, 130, 155, 160, 640, 250}.
Can you please look into this?

hermann@7600x:~/RSA_numbers_factored/pari$ gp -q RSA_numbers_factored.gp 
4sq.gp
? foreach(RSA.factored([1,1]),r,[l,n]=r;print1(l,":",#threesquares(n)," 
"))
59:3 129:1 180:3 230:3 768:3
? foreach(RSA.factored([3,3]),r,[l,n]=r;print1(l,":",#threesquares(n)," 
"))
130:1 155:1 160:1 190:3 640:1 220:3 250:1
?

For the result vectors of length 3, the sum of squares matches n and is 
correct:

? 
foreach(RSA.factored(1),r,[l,n]=r;F=threesquares(n);if(#F==3,print1(vecsum([x^2|x<-F])==n)))
111111
?

Regards,

Hermann.