Re: sqrt(x,n) for non-prime n?

[hermann@stamm-wilbrandt.de]

On 2023-11-21 14:21, Bill Allombert wrote:
> On Tue, Nov 21, 2023 at 09:35:53AM +0100, hermann@stamm-wilbrandt.de 
> wrote:
> > Modular sqrt does not work with non-prime modulus:
> > ...
>
> Indeed, but you can do
>
> ? issquare(Mod(-1,125),&z)
> %3 = 1
> ? z
> %4 = Mod(57,125)
Thank you, that is wonderful, here with example for Kunerth's wikipedia 
page:

? issquare(Mod(41,856),&z)
1
? z
Mod(345, 856)
?


> The problem is that when given Mod(a,b) we do not want to have to test
> b for primality each time...
Totally understood.

A short hint to issquare(...) solution would be helpful somewhere here:
...
  *** sqrt: not a prime number in sqrt [modulus]: 125.
  ***   Break loop: type 'break' to go back to GP prompt
break>


I had just completed implementing "sqrtm(x)", this time with help text:

$ gp -q sqrtm.gp
? ?sqrtm
sqrtm(x): square root of x (x.mod not required to be prime).

? sqrtm(Mod(41,856))
Mod(345, 856)
? sqrtm(Mod(41,856))^2
Mod(41, 856)
?

Not needed anymore with "issquare(...)" computation available, was a 
nice exercise:

$ cat sqrtm.gp
sqrtm(x,s1,f)={
  if(type(x)=="t_INTMOD",sqrtm(lift(x),Mod(0,1),factor(x.mod)),
    s2=sqrt(x+O(f[1,1]^f[1,2]));
    ch=chinese(s1,Mod(s2%s2.mod,f[1,1]^f[1,2]));
    if(#f[,1]==1,ch,sqrtm(x,ch,f[2..#f,])))
}
addhelp(sqrtm, "sqrtm(x): square root of x (x.mod not required to be 
prime).");
$

Regards,

Hermann.