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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Oct 09, 2023 at 03:04:10PM +0200, hermann@stamm-wilbrandt.de wrote:
> Hi Bill,
> 
> So wrong result for RSA-x with x in {129, 130, 155, 160, 640, 250}.
> Can you please look into this?

Indeed, I forgot a flag in twosquares (to allow imprimitive solutions)
I join a fixed version.

Cheers,
Bill

twosquares(n)=abs(qfbsolve(Qfb(1,0,1),n,2))
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));
  my(P=4*randomprime(2^500,Mod(1,4)));
  my(F=twosquares(P));
  if (#F!=2 || norml2(F)!=P,error("twosquares",P));
}