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

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

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]);
> 
> It has interesting property wrt odd semiprimes being product of two primes
> =1 (mod 4):

All these numbers are sum of two squares.

> I asked for foursquare() for applying to unfactored RSA-numbers =1 (mod 4) >
> RSA-250.
> Unfortunately that is not possible, since qfsolve() does first factor the
> determinant
> of passed matrix, which is -n. Find details in P.S: of this posting:
> https://www.mersenneforum.org/showthread.php?t=28910
> 
> Same posting is on Lagrange's three square theorem.
> I describe there how I found original 1798 french text online on internet
> archive.
> 
> I am not sure how to make foursquare(n) efficient (faster than factoring n).
> Perhaps the prove of theorem "Odd integer not being 8n+7 is sum of 3
> squares"
> on page 398 will help to get efficient threesquare1m4(n).

You could use

threesquare(n) = abs(qfsolve(matdiagonal([1,1,1,-n]))[1..3]);

but it is not faster.

But you can try this one:

foursquarep(n)=
{
  for(i=1,sqrtint(n),
    if(ispseudoprime(n-i^2),return(concat(i,threesquare(P-i^2)))))
}

or even

foursquaref(n)=
{
  for(i=1,sqrtint(n),
    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))))));
}

Cheers,
Bill.