Re: foursquares.gp

[hermann@stamm-wilbrandt.de]

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.