Shanks-Tonelli AlgorithmDate: 01/17/2001 at 09:43:00 From: Alexander Klink Subject: Calculation square roots modulo n, where n = p*q Hi, I want to implement a fair coin flip algorithm from "Applied Cryptography." I therefore need to calculate the four square roots of a number modulo n. I know that n = p*q, and therefore I could calculate them modulo p and modulo q, which are primes, so I have field, but I still have no idea how to do this. Maybe you've got an idea. Alex Date: 01/17/2001 at 12:01:19 From: Doctor Rob Subject: Re: Calculation square roots modulo n, where n = p*q Thanks for writing to Ask Dr. Math, Alex. If GCD(2*A,n) > 1, then A has fewer than four square roots (mod n), so we must assume that GCD(2*A,n) = 1. Furthermore, A has a square root modulo prime P if and only if the Legendre symbol (A/P) = +1. If either of these conditions with P = p and P = q fails, then A has no square roots modulo n = p*q. I like the Shanks-Tonelli Algorithm (given below) for finding X, a square root of A (mod P) where P is an odd prime. Once you have used Shanks-Tonelli with P = p to find y such that: y^2 = A (mod p) and used it again with P = q to find z such that: z^2 = A (mod q) then use the Chinese Remainder Theorem to find x (mod p*q) such that: x = y (mod p) x = z (mod q) Then this x satisfies x^2 = A (mod n), and so does n - x. Also find x' (mod p*q) such that: x' = -y (mod p) x' = z (mod q) Then this x' also satisfies x'^2 = A (mod n), and so does n - x'. Thus the four square roots are x, n - x, x', and n - x' (mod n). The Shanks-Tonelli Algorithm ---------------------------- Factor P - 1 = 2^S*Q, where Q is odd, and S >= 1. Start with an approximate root: R = A^([Q+1]/2) (mod P) If S = 1, we are done, and X = R is the solution. Find a quadratic nonresidue W (mod P) by guessing a W and seeing whether or not the Legendre symbol (W/P) = -1, until you find one for which this is true. Set V = W^Q (mod P). Also compute: A^(-1) = A^(P-2) (mod P) Then we are ready to begin. Compute: (R^2*A^[-1])^(2^I) (mod P) for I = 0, 1, 2, ..., S-1 by repeatedly squaring, and find the first one which is 1. Say: (R^2*A^[-1])^(2^T) = 1 (mod P) is the first. If T = 0, we are done, and X = R is the solution. If T > 0, set: R' = R*V^(2^[S-T-1]) (mod P) computed by squaring V S-T-1 times, and then multiplying by R. This R' is a better approximation to the square root than R was. Replace R by R', and repeat. When this procedure ends, you will have X such that X^2 = A (mod P). - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/