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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Apr 28, 2026 at 09:03:26PM +0200, hermann@stamm-wilbrandt.de wrote:
> ? sqrt(Mod(-1-2^4,3*17))
> %1 = Mod(17, 51)
> ? sqrt(Mod(-1-2^2,3*17))
>   ***   at top-level: sqrt(Mod(-1-2^2,3*17))
>   ***                 ^----------------------
>   *** sqrt: not a prime number in sqrt [modulus]: 51.
>   ***   Break loop: type 'break' to go back to GP prompt
> break>
> 
> 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