6 Jan
2005
6 Jan
'05
7:41 a.m.
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)?