Re: foursquares.gp

[hermann@stamm-wilbrandt.de]

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?


https://github.com/Hermann-SW/RSA_numbers_factored

hermann@7950x:~/RSA_numbers_factored/pari$ gp -q foursquares.gp 
RSA_numbers_factored.gp
? [l,n]=RSA.get(59);
? twosquares(n)
[250662312444502854557140314865, 93861205413769670113229603198]
? ##
  ***   last result computed in 1,584 ms.
? foreach(RSA.factored(1),r,[l,n]=r;print1(l," ");)
59 129 130 155 160 180 190 640 220 230 768 250
?


Regards,

Hermann.