Shanks-Tonelli algorithm

From Wikipedia, the free encyclopedia

The Shanks-Tonelli algorithm is used within modular arithmetic to solve a congruence of the form

$x^2 \equiv n \mod p$

where n is a quadratic residue (mod p), and $p$ is prime; typically, $p \equiv 1 \mod 4$ .

When $p \equiv 3 \mod 4$ , it is much more efficient to use the following identity: $x \equiv n^{\frac{p+1}{4}} \mod p$ .

Shanks-Tonelli cannot be used for composite moduli, which is a problem equivalent to integer factorization.

1 The algorithm
2 Uses
3 Generalization
4 External links

[edit] The algorithm

Inputs: p, an odd prime. n, an integer which is a quadratic residue (mod p), meaning that the Legendre symbol (n/p) = 1.

Outputs: R, an integer satisfying $R^2 \equiv n \mod p$ .

Factor out powers of 2 from (p-1), defining Q and S as: $p - 1 = Q 2 S$ .
Select a W such that the Legendre symbol (W/p) = -1 (that is, W should be a quadratic non-residue modulo p).
Let $R = n^{\frac{Q+1}{2}} \mod p$ .
Let $V = W^Q \mod p$ .
Loop:
1. Find the lowest i, $0 \leq i \leq n-1$ , such that $(R^2n^{-1})^{2^{i}} \equiv 1 \mod p$ . This can be done efficiently by starting with $R 2 n - 1$ and squaring (mod p) until the result is 1.
2. If $i = 0$ , return R.
3. Otherwise, let $R' = RV^{2^{S-i-1}} \pmod{p}$ and repeat the loop with R' as the new R.

[edit] Uses

Modular square roots are used in, for example, the quadratic sieve and related integer factorization algorithms.

[edit] Generalization

Shanks-Tonelli can be generalized to any cyclic group (instead of $\mathbb{Z}/p\mathbb{Z}^*$ ) and to k-th roots for arbitrary integer k, in particular to taking the k-th root of an element of a Finite field.