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

[hermann@stamm-wilbrandt.de]

On 2023-11-21 11:56, hermann@stamm-wilbrandt.de wrote:
> Thank you — every day something new to learn with PARI/GP.
> I have not used p-adic numbers until now.
>
> ? s=sqrt(-1+O(5^3))
> %26 = 2 + 5 + 2*5^2 + O(5^3)
> ? s%s.mod
> %27 = 57
> ? Mod(s%s.mod,5^3)^2
> %28 = Mod(124, 125)
> ? Mod(s,5^3)^2
> %29 = Mod(124, 125)
> ?
>
> What can be done if modulus is not a p-adic number?
> Like n=856 in example of:
> https://en.m.wikipedia.org/wiki/Kunerth%27s_algorithm
>
> sqrt(41) (mod 856) is 345, can that be determined with PARI/GP somehow?
>
> ? Mod(345,856)^2
> %30 = Mod(41, 856)
> ?
Wow, just played a bit and learned how to compute sqrt(41) (mod 856) 
with PARI/GP:

? factor(856)
%1 =
[  2 3]

[107 1]

? s1=sqrt(41+O(2^3))
%2 = 1 + O(2)
? s2=sqrt(41+O(107))
%3 = 24 + O(107)
? chinese(Mod(s1%s1.mod,2^3),Mod(s2,s2.mod))
%4 = Mod(345, 856)
? chinese(Mod(s1%s1.mod,2^3),Mod(s2,s2.mod))^2
%5 = Mod(41, 856)
?


So implementing Kunerth's method is only needed if factoring modulus 
would take too much time.

Regards,

Hermann.