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 whetherPARI/GP allows to compute sqrt(x,n) somehow (with known factorization of n)?