Re: square roots mod p.
From: Arturo Magidin (magidin_at_math.berkeley.edu)
Date: 06/04/04
- Next message: Robert Israel: "Re: Asymptotic Behaviour for Integral"
- Previous message: Dale Henderson: "square roots mod p."
- In reply to: Dale Henderson: "square roots mod p."
- Next in thread: Robin Chapman: "Re: square roots mod p."
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 4 Jun 2004 20:57:55 +0000 (UTC)
In article <87ekovw16c.fsf@camel.tamu-commerce.edu>,
Dale Henderson <nilram@hotpop.com> wrote:
>I'm looking for a algorithm to compute the square root of a number mod
>a prime. I know I can determine whether or not a number has a square
>root using the Legendre symbol. But I want to know what the actual
>root is.
>
>For example how would one find that the square root of 2 is 3 mod
>7.
For small p, you are better off just squaring and checking; otherwise,
the algorithm in the "Handbook of Applied Cryptography" by Menezes,
van Oorschot, and Vanstone (fifth printing, 2001)
http://www.cacr.math.uwaterloo.ca/hac/
has the following algorithm, assuming you already computed the
Legendre symbol of a mod p and found that a is a quadratic residue
(pp. 100-101, in Chapter 3):
1. Randomly select integers b, 0< b < p, until you find one that is
not a quadratic residue mod p (you check this via the Legendre
symbol).
2. Write p-1 = 2^s* t, where t is odd.
3. Compute the multiplicative inverse of a mod p via the Extended
Euclidean Algorithm.
4. Set c = b^t (mod p) and r = a^{(t+1)/2} (mod p).
5. For i = 1 to s-1, do the following:
(i) Compute d = (r^2*a^{-1})^{2^{s-1-i}} (mod p).
(ii) If d = -1 (mod p), then replace r with r*c (mod p).
(iii) Replace c with c^2 (mod p).
6. When you are done, the numbers r and -r (mod p) are the square
roots of a mod p.
As far as it was known when HAC was printed, there are no known
polynomial time algorithms for finding a quadratic non-residue mod p,
which is necessary for step 1. The expected running time of the
algorithm is O((log p)^4).
There is a simpler algorithm when p= 3 (mod 4); in that case, the two
square roots of a modulo p (assuming a is a quadratic residue) are
a^{(p+1)/4} and -a^{(p+1)/4}.
If p = 5 (mod 8), then you can also get a deterministic algorithm:
1. Compute d=a^{(p-1)/4} (mod p).
2. If d=1, compute r = a^{(p+3)/8} (mod p).
3. If d= p-1, compute r = 2a(4a)^{(p-5)/8} (mod p).
4. In either case, r and -r are the two square roots of a mod p.
Finally, if p-1= 2^s*t with s large, then you have an algorithm with
expected running time of O( (log p)^3), preferable to the first one
above, as follows:
1. Choose a random b, 1<= b <= p-1, until b^2-4a is a quadratic
non-residue mod p.
2. Let f(x) be the polynomial f(x) = x^2 - bx + a in (Z/pZ)[x].
3. Compute r = x^{(p+1)/2} (mod f(x)); r will be an integer.
4. r and -r are the two square roots of a modulo p.
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu
- Next message: Robert Israel: "Re: Asymptotic Behaviour for Integral"
- Previous message: Dale Henderson: "square roots mod p."
- In reply to: Dale Henderson: "square roots mod p."
- Next in thread: Robin Chapman: "Re: square roots mod p."
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
