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

[Aurel Page <aurel.page@normalesup.org>]

Dear Hermann,

You can use 5-adics:
? sqrt(-1+O(5^3))
% = 2 + 5 + 2*5^2 + O(5^3)

Best,
Aurel

On 21/11/2023 09:35, hermann@stamm-wilbrandt.de wrote:
> Modular sqrt does not work with non-prime modulus:
>
> ? sqrt(Mod(-1,125))
>   ***   at top-level: sqrt(Mod(-1,125))
>   ***                 ^-----------------
>   *** sqrt: not a prime number in sqrt [modulus]: 125.
>   ***   Break loop: type 'break' to go back to GP prompt
> break>
>
> There is a solution:
>
> ? Mod(57,125)^2
> %3 = Mod(124, 125)
> ?
>
> Kunerth's 1877 method allows to compute eg sqrt(41) (mod 856):
> https://en.m.wikipedia.org/wiki/Kunerth%27s_algorithm
>
> That method does not even require to know factorization of modulus.
>
> Before I implement that method in PARI/GP I want to ask whether
> PARI/GP allows to compute sqrt(x,n) somehow (with known factorization 
> of n)?