John Cremona on Sat, 07 Oct 2023 11:50:04 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

It's nice to see that an old talk by a Warwick student is still useful!

For solving quadratic forms without factoring, see the work of Denis Simon (who reads this list), as well as one of my papers, though that would give you rational rather than integral solutions.

John Cremona 

On Fri, 6 Oct 2023, 18:54 Bill Allombert, <Bill.Allombert@math.u-bordeaux.fr> wrote:
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