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

[hermann@stamm-wilbrandt.de]

On 2026-04-28 10:26, Bill Allombert wrote:
> 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 ?
The "?? sqrt" doc states for Intmod that p is a prime.
For nearly all nonprimes as modulus an error message is raised.
And the behavior for modulus 3*17 is contradictory:

? 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.


Regards,

Hermann.