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

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

On Fri, Oct 06, 2023 at 06:41:49PM +0200, hermann@stamm-wilbrandt.de wrote:
> > ... but suboptimal, we should start by the largest i, so that P is as
> > small as possible!
> > 
> > foursquaref(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,threesquare(P))))));
> > }
> > 
> I tried that, for some values >100x faster than the other.
> But still not good for really large numbers.
> 
> All but first Mersenne prime are =7 (mod 8), so needing 4 squares.
> I tried some Mersenne primes 2^p-1 on fast AMD 7600X CPU:
> 
> p       time [min]
> 11213	0:02
> 21701	1:12
> 44497	2:08
> 86243   stooped after 46:00

If your number is prime, you do not need to use foursquaref, you can use foursquare
since you know the factorization!

? foursquare(2^86243-1);
##
***   last result computed in 2min, 30,519 ms.

(the only bug is that qfsolve should allow the user to provide the factorization of the
discriminant, this would save 40s).

Cheers,
Bill