Shanks-Tonelli Algorithm

Date: 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/