Re: foursquares.gp

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

On Fri, Dec 01, 2023 at 09:14:10AM +0100, hermann@stamm-wilbrandt.de wrote:
> On 2023-11-19 00:28, hermann@stamm-wilbrandt.de wrote:
> > Bill did develop and tuned foursquares.gp based on this thread:
> > https://pari.math.u-bordeaux.fr/archives/pari-users-2310/msg00003.html
> > 
> > You can find foursquares.gp in contributed GP scripts section:
> > https://pari.math.u-bordeaux.fr/Scripts/
> > https://pari.math.u-bordeaux.fr/Scripts/foursquares.gp
> > 
> > 
> Bill's implementation of "twosquares()" in foursquares.gp:
> 
> twosquares(n)=abs(qfbsolve(Qfb(1,0,1),n,2));
> 
> I looked up source code, and one of the first steps is to factor n.
> This is an option for small RSA-59, but does not work for next
> RSA number =1 (mod 4), RSA-129 takes endless time:
> (3:11:10h on 12T 7600X CPU with multithreaded cado-nfs.py)
> 
> Is there any other more performant method to find (one) sum of squares
> for semiprime of two primes, each =1 (mod 4)?
> 
> I know that determining both such sums (ther are exactly two) allows to
> factor easily.
> But knowing one does not allow to factor, so can it be computed efficiently?

Let N=p*q with p,q arbitrary prime.
If you manage to write N = a^2+b^2, you prove that both p and q are 1 mod 4.
But this is not something we know about a RSA number a priori.
So I do not think anybody knows the answer.

Cheers,
Bill