Shanks-Tonelli algorithm

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

:$x^2\; equiv\; n\; pmod\; p$

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

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

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

Once you have solved the congruence for "x" the second solution is simply .

If the Generalized Riemann hypothesis is true, the Shanks-Tonelli algorithm is guaranteed to run in polynomial time.

The algorithm was developed by Alberto Tonelli and refined by Daniel Shanks.

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\; pmod\; p$.

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

Uses

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

Generalization

Shanks-Tonelli can be generalized to any cyclic group (instead of $mathbb\{Z\}/pmathbb\{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.

References

* cite book
last=Niven
first=Ivan
authorlink=Ivan Niven
coauthors=Herbert S. Zuckerman, Hugh L. Montgomery
title=An Introduction to the Theory of Numbers
edition=5th edition
year=1991
publisher=Wiley
isbn=0-471-62546-9Pages 110–115 describe the algorithm and explain the group theory behind it.

External links

* [http://edmond.bf.rmit.edu.au/ecommerce/QS/QSNotes.htm Quadratic Sieve Algorithm] - contains a description of the Shanks-Tonelli algorithm.