hermann on Fri, 01 Dec 2023 09:14:15 +0100

 Re: foursquares.gp

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Re: foursquares.gp
• From: hermann@stamm-wilbrandt.de
• Date: Fri, 01 Dec 2023 09:14:10 +0100
• Delivery-date: Fri, 01 Dec 2023 09:14:15 +0100
• References: <207df5ff21dfc8de891eabc538a770c5@stamm-wilbrandt.de>
• User-agent: Roundcube Webmail/1.4.13

```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:

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.

```