Associated Topics || Dr. Math Home || Search Dr. Math

### Shanks-Tonelli Algorithm

```
Date: 01/17/2001 at 09:43:00
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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search