An equivalent, but slightly more redundant version of this algorithm was developed by Alberto Tonelli in 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
Operations and comparisons on elements of the multiplicative group of integers modulo p are implicitly mod p.
- p, a prime
- n, an element of such that solutions to the congruence r2 = n exist; when this is so we say that n is a quadratic residue mod p.
Outputs: r in such that r2 = n
- By factoring out powers of 2, find Q and S such that p-1 = Q2S with Q odd
- Search for a z in which is a quadratic non-residue
- If t = 1, return r = R
- Otherwise, use repeated squaring to find the least i, 0 < i < M, such that
- Let , and set
Once you have solved the congruence with r the second solution is p − r. If the least i such that is M, then no solution to the congruence exists, ie n is not a quadratic residue.
This is most useful when p ≡ 1 (mod 4); for primes such that p ≡ 3 (mod 4), this reduces to finding .
We can show that at the start of each iteration of the loop the following loop invariants hold:
- (since z is a quadratic nonresidue, per Euler's criterion)
- (since n is a quadratic residue)
At each iteration, with M' , c' , t' , R' the new values replacing M, c, t, R:
- since we have that but (i is the least value such that )
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.
Order of t
We can alternately express the loop invariants using the order of the elements:
- as before
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.
Solving the congruence r2 ≡ 5 (mod 41). 41 is prime as required and 41 ≡ 1 (mod 4). 5 is a quadratic residue by Euler's criterion: (as before, operations in are implicitly mod 41).
- so ,
- Find a value for z:
- , so 2 is a quadratic residue by Euler's criterion.
- , so 3 is a quadratic nonresidue: set
- First iteration:
- , so we're not finished
- , so
- Second iteration:
- , so we're still not finished
- Third iteration:
- , and we are finished; return
- First iteration:
Indeed, 282 ≡ 5 (mod 41) and (-28)2 ≡ 132 ≡ 5 (mod 41). So the algorithm yields the two solutions to our congruence.
Speed of the algorithm
The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues))
modular multiplications, where is the number of digits in the binary representation of and is the number of ones in the binary representation of . If the required quadratic nonresidue is to be found by checking if a randomly taken number is a quadratic nonresidue, it requires (on average) computations of the Legendre symbol. The average of two computations of the Legendre symbol are explained as follows: is a quadratic residue with chance , which is smaller than but , so we will on average need to check if a is a quadratic residue two times.
This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus is random, that is, if is not particularly large with respect to the number of digits in the binary representation of . As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) . However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of , one may replace with an expression that is asymptotically bounded by . Explicitly, one computes such that and then satisfies (note that is a multiple of 2 because is a quadratic residue).
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 , making it possible to check every up to that limit and find a suitable within polynomial time. Keep in mind, however, that this is a worst-case scenario; in general, is found in on average 2 trials as stated above.
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. It is also useful for the computations in the Rabin cryptosystem.
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.
- Factor out powers of 2 from p − 1, defining Q and S as: with Q odd.
- Find from the table such that and set
- return R.
- Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.
- Daniel Shanks. Five Number-theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.
- Gonzalo Tornaria - Square roots modulo p, page 2 http://www.springerlink.com/content/xgxe68edy03la96p/fulltext.pdf
- Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80: 477–500, doi:10.1090/s0025-5718-10-02356-2
- Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, JSTOR 2008811, doi:10.2307/2008811
- Adleman, L. M., K. Manders, and G. Miller: 1977, `On taking roots in finite fields'. In: 18th IEEE Symposium on Foundations of Computer Science. pp. 175-177
- Ivan Niven,; Herbert S. Zuckerman,; Hugh L. Montgomery (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley. ISBN 0-471-62546-9.
Pages 110–115 describe the algorithm and explain the group theory behind it.
- Daniel Shanks. Five Number Theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.
- Alberto Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen. Pp. 344–346. 1891. 
- Gagan Tara Nanda - Mathematics 115: The RESSOL Algorithm