hermann on Tue, 21 Nov 2023 09:35:57 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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


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