Re: Which unfactored sofar RSA numbers have sum of squares representation?

[hermann@stamm-wilbrandt.de]

RSA_numbers_factored repo RSA.totient() function
allows to efficiently compute GP eulerphi() by making use
of the stored prime factors for each factored RSA number.

RSA.reduced_totient() is efficiently computed Charmichael
function, also based on stored prime factors.

It seems that 4 dividing quotient of both functions allows
to tell that the corresponding RSA number has sum of squares
representation. Unfortunately for this knowledge of prime
factors is necessary as in previous posting:

? foreach(RSA.factored(1),r,[l,n,p,q]=r;\
    print(l," ",RSA.totient(r)/RSA.reduced_totient(r)," ",p%4,",",q%4))
59 4 1,1
129 4 1,1
130 2 3,3
155 2 3,3
160 2 3,3
180 8 1,1
190 26 3,3
640 2 3,3
220 2 3,3
230 4 1,1
768 4 1,1
250 2 3,3
?

None of RSA-numbers =3 (mod 4) has sum of squares representations,
and none have 4 as divider of the quotient:

? foreach(RSA.factored(3),r,[l,n,p,q]=r;\
    print(l," ",RSA.totient(r)/RSA.reduced_totient(r)," ",p%4,",",q%4))
79 6 1,3
100 2 3,1
110 2 3,1
120 2 3,1
140 2 3,1
150 2 1,3
170 22 3,1
576 2 1,3
200 2 1,3
210 2 3,1
704 2 1,3
232 2 3,1
240 2 1,3
?


Regards,

Hermann.


On 2023-08-12 18:19, hermann@stamm-wilbrandt.de wrote:
> A requirement for sum of squares representation of n=RSA-l is, that 
> n%4==1.
>
> Here are all (un)factored sofar RSA numbers that are =1 (mod 4).
> Separation possible by nrp = Mod(qnr, n)^(phi/4), with qnr a quadratic
> non-residue (mod n), and phi=(p-1)*(q-1).
> But knowing n=p*q is required.
> If p==1 (mod 4) and q==1 (mod 4), p and q have unique sum of squares.
> And by Brahmagupta–Fibonacci identity n has two representations as sum
> of squares.
> If p==3 (mod 4) and q==3 (mod 4), n does not have sum of squares 
> representation.
>
> pi@pi400-64:~/RSA_numbers_factored/pari $ gp -q < phi.gp
> validate(rsa): ✓
> RSA p%4 q%4 nrp
>  59   1   1   1
> 129   1   1   1
> 130   3   3  -1
> 155   3   3  -1
> 160   3   3  -1
> 180   1   1   1
> 190   3   3  -1
> 640   3   3  -1
> 220   3   3  -1
> 230   1   1   1
> 768   1   1   1
> 250   3   3  -1
> 280
> 309
> 310
> 320
> 340
> 360
> 370
> 390
> 430
> 450
> 460
> 1536
> 470
> 500
> 617
> 2048
> pi@pi400-64:~/RSA_numbers_factored/pari $
>
>
>
> pi@pi400-64:~/RSA_numbers_factored/pari $ cat phi.gp
> \r RSA_numbers_factored
> print("RSA p%4 q%4 nrp");
> for(i=1,#rsa,\
>   if(#rsa[i]>=4,\
>     [l,n,p,q]=rsa[i];\
>     forprime(t=2,oo,if( kronecker(t, p)==-1, qnrp=t; break()));\
>     assert(Mod(qnrp, p)^((p-1)/2) == Mod(-1, p));\
>     forprime(t=2,oo,if( kronecker(t, q)==-1, qnrq=t; break()));\
>     assert(Mod(qnrq, q)^((q-1)/2) == Mod(-1, q));\
>     m = chinese(Mod(qnrp, p), Mod(qnrq, q));\
>     qnr = lift(m);\
>     assert(Mod(qnr, n) == m);\
>     phi=(p-1)*(q-1);\
>     assert(Mod(qnr, n)^(phi/2) == 1);\
>     if(n%4==3, next);\
>     printf("%3d %3d %3d %3d\n", l, p%4, q%4, centerlift(Mod(qnr, 
> n)^(phi/4))),\
>     [l,n]=rsa[i];if(n%4==1,print(l));\
>   )\
> )
> pi@pi400-64:~/RSA_numbers_factored/pari $
>
>
>
> Regards,
>
> Hermann.