hermann on Fri, 01 Dec 2023 10:40:57 +0100

 Re: foursquares.gp

```On 2023-12-01 09:54, Bill Allombert wrote:
```
```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

```
```You are right, I did post my query wrong.

```
For the factored sofar RSA numbers we know when both prime factors are 1 mod 4:
```
? foreach(RSA.factored([1,1]),r,[l,n]=r;print1(l," ");)
59 129 180 230 768
?

```
Only for the unfactored sofar we do not know, these are the only [1,1] candidates:
```
? foreach(RSA.unfactored(1),r,[l,n]=r;print1(l," ");)
280 309 310 320 340 360 370 390 400 430 450 460 1536 470 500 617 2048
?

So to make my twosquares question more precise, is there an algorithm
that can compute one of the two sums of squares for RSA-129 in time <1h?

```
Knowing factorization allows to compute both sum of two squares in milliseconds:
```
\$ gp -q RSA_numbers_factored.gp
? r=RSA.get(129);
? [l,n,p,q]=r;
? l==#digits(n)&&n==p*q
1
? [e,f]=RSA.square_sums(r);
? ##
***   last result: cpu time 27 ms, real time 37 ms.
? [a,b]=e;[c,d]=f;
? (a^2+b^2)==n&&(c^2+d^2)==n
1
? #Set([a,b,c,d])
4
? e
```
[4884133573015746876620685320022337791674591352270255994218129815, 9514560683438269061040235120994472790697558813773717993532826646]
```?

```
RSA.square_sums() uses Brahmagupta–Fibonacci identity to compute from sum of two
```squares of each prime factor.

Sum of two squares for prime from sqrt(-1) (mod p) can be determined
```
super efficiently with halfgcd(), but current implementation uses ggcd() instead:
```
sq2(p)=
{
\\  """determine pair of numbers, their squares summing up to p"""
assert(p>1&&p%4==1,p," not 1 (mod 4)");
my(a=root4m1(p),x,y);
[x,y]=ggcd([p,0],[a,1]);
[abs(x),abs(y)];
}

Regards,

Hermann.

```