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 08:45:58AM +0200, hermann@stamm-wilbrandt.de wrote:
> Seems to be a little bug.
> I found another factor than 3 that worked but not able to reproduce now.
> Not all primes of the form 1+k^2 behave wrong as k=6 shows:
> 
> ? version
> [2, 17, 3]
> ? sqrt(Mod(-1-2^2,3*5))
> Mod(5, 15)
> ? sqrt(Mod(-1-2^4,3*17))
> Mod(17, 51)
> ? sqrt(Mod(-1-10^2,3*101))
> Mod(101, 303)
> ? sqrt(Mod(-1-2^6,3*37))
>   ***   at top-level: sqrt(Mod(-1-2^6,3*37))
>   ***                 ^----------------------
>   *** sqrt: not a prime number in sqrt [modulus]: 111.

What is the bug, from your point of view ?

>From my point of view, the issue is that there is no dedicated GP type for Z/pZ
with p prime, and for some operations with Z/nZ it is important to know the
factorization of n, which is not part of INTMOD.

So sqrt(Mod()) assumes than n is prime, but issquare(Mod()) does not!

? issquare(Mod(-1-2^6,3*37),&z);z
%1 = Mod(40,111)

and issquare does not allow to pass the factorization of n.

Cheers,
Bill