The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p. Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization.
[1] An equivalent, but slightly more redundant version of this algorithm was developed by Alberto Tonelli[2][3] in 1891.
The version discussed here was developed independently by Daniel Shanks in 1973, who explained: My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned.
[4] According to Dickson,[3] Tonelli's algorithm can take square roots of x modulo prime powers pλ apart from primes.
(which will always be odd), Euler's criterion tells us that
has no square root (is a non-residue), Euler's criterion tells us that: It is not hard to find such
With a little bit of variable maintenance and trivial case compression, the algorithm below emerges naturally.
Operations and comparisons on elements of the multiplicative group of integers modulo p
are implicitly mod p. Inputs: Outputs: Algorithm: Once you have solved the congruence with r the second solution is
is M, then no solution to the congruence exists, i.e. n is not a quadratic residue.
We can show that at the start of each iteration of the loop the following loop invariants hold: Initially: At each iteration, with M' , c' , t' , R' the new values replacing M, c, t, R: From
and the test against t = 1 at the start of the loop, we see that we will always find an i in 0 < i < M such that
M is strictly smaller on each iteration, and thus the algorithm is guaranteed to halt.
When we hit the condition t = 1 and halt, the last loop invariant implies that R2 = n. We can alternately express the loop invariants using the order of the elements: Each step of the algorithm moves t into a smaller subgroup by measuring the exact order of t and multiplying it by an element of the same order.
The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues)) modular multiplications, where
[5] The average of two computations of the Legendre symbol are explained as follows:
This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus
is not particularly large with respect to the number of digits in the binary representation of
However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of
The algorithm requires us to find a quadratic nonresidue
There is no known deterministic algorithm that runs in polynomial time for finding such a
However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue
The Tonelli–Shanks algorithm can (naturally) be used for any process in which square roots modulo a prime are necessary.
For example, it can be used for finding points on elliptic curves.
) and to kth roots for arbitrary integer k, in particular to taking the kth root of an element of a finite field.
[8] If many square-roots must be done in the same cyclic group and S is not too large, a table of square-roots of the elements of 2-power order can be prepared in advance and the algorithm simplified and sped up as follows.
According to Dickson's "Theory of Numbers"[3] A. Tonelli[9] gave an explicit formula for the roots of
[3] The Dickson reference shows the following formula for the square root of
and Dickson also attributes the following equation to Tonelli: Using
the math follows: First, find the modular square root mod