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

On 2026-04-28 10:26, Bill Allombert wrote:
> On Tue, Apr 28, 2026 at 08:45:58AM +0200, [email protected] 
> 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.