[math-fun] Modular square root
Is there a fairly fast algorithm to find the square root of a number to a given prime modulus p?
Thu, 6 Jan 2005 09:25:44 -0500 "David Wilson" <davidwwilson@comcast.net> Is there a fairly fast algorithm to find the square root of a number to a given prime modulus p? "the"? Won't there be p square roots for each number mod p? If 0 <= x < p, and r = x^{1/2}, then won't (x+ip)^{1/2} for i =0, ... (p-1) also be sqrt(x) mod p (and they're all distinct)? I'm curious about the question, though: when you say "fairly fast algorithm", are you looking for something faster than sqrt of (x mod p)? (or sqrt of ((x mod p) + i p)?
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.
Thu, 6 Jan 2005 10:08:07 -0500 Michael Kleber <michael.kleber@gmail.com> 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. Yes, thanks. Without thinking too hard about it, I assumed he was asking for real roots mod p.
On Thu, 6 Jan 2005, David Wilson wrote:
Is there a fairly fast algorithm to find the square root of a number to a given prime modulus p?
http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf, section 3.5, contains some algorithms...
participants (4)
-
David Wilson -
Helger Lipmaa -
Michael B Greenwald -
Michael Kleber