Re: modular sqrt does not always detect and error on non-prime modulus

[hermann@stamm-wilbrandt.de]

On 2026-04-28 21:25, Bill Allombert wrote:
...
> > One fix could be that you close the whole in detecting non-prime 
> > modulus.
> > The other fix would be to allow sqrt(Mod(a,np)) for nonprimes np.
> > But the error that gets raised normally seems to have a reason.
>
> The problem is that it is more costly to check whether p is prime than
> to compute
> the square root.
> Sometime we are lucky and the algorithm find a proof that p is not
> prime, so we can
> return an error.
>
> Cheers,
> Bill
Thanks, OK.

Perhaps a small hint in "??sqrt" of GP doc on behavior for non primes?


sqrt(-1) always exists for primes =1 (mod 4).

Modular square root results can be checked by squaring fast.
As shown for all RSA numbers =1 (mod 4):
https://github.com/Hermann-SW/RSA_numbers_factored


hermann@7950x:~/RSA_numbers_factored/pari$ gp -q RSA_numbers_factored.gp
? forprime(p=5,500,if(p%4==1,print1(sqrt(Mod(-1,p))^2==Mod(-1,p))))
11111111111111111111111111111111111111111111
? 
foreach(RSA.factored(mod4=1),t,n=t[2];print1(sqrt(Mod(-1,n))^2==Mod(-1,n)))
000000000000
? ##
  ***   last result: cpu time 1 ms, real time 3 ms.
? 
foreach(RSA.unfactored(mod4=1),t,n=t[2];print1(sqrt(Mod(-1,n))^2==Mod(-1,n)))
00000000000000000
? ##
  ***   last result: cpu time 15 ms, real time 15 ms.
? R=RSA.unfactored(mod4=1);[l,n]=R[#R];print(l)
2048
?

Regards,

Hermann.