6 Jan
2005
6 Jan
'05
8:08 a.m.
David Wilson asked:
Is there a fairly fast algorithm to find the square root of a number to a given prime modulus p?
See the sci.math discussion archived at http://www.math.niu.edu/~rusin/known-math/94/sqrt.mod Michael Greenwald said:
"the"? Won't there be p square roots for each number mod p?
No, there will be at most two. Working mod p, you can still do a^2=b^2 a^2-b^2=0 (a+b)(a-b)=0 a=b or a=-b, since there are no zero divisors mod p. Perhaps you didn't realize that David is asking for roots in the integers mod p. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.