hermann on Fri, 01 Dec 2023 10:40:57 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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 determinedsuper 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.