Tonelli–Shanks algorithm


The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n, 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.
An equivalent, but slightly more redundant version of this algorithm was developed by
:it:Alberto Tonelli|Alberto Tonelli
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.

According to Dickson, Tonelli's algorithm can take square roots of x modulo prime powers pλ apart from primes.

Core ideas

Given a non-zero and an odd prime, Euler's criterion tells us that has a square root if and only if:
In contrast, if a number has no square root, Euler's criterion tells us that:
It is not hard to find such, because half of the integers between 1 and have this property. So we assume that we have access to such a non-residue.
By dividing by 2 repeatedly, we can write as, where is odd. Note that if we try
then. If, then is a square root of. Otherwise, for, we have and satisfying:
If, given a choice of and for a particular satisfying the above, we can easily calculate another and for such that the above relations hold, then we can repeat this until becomes a -th root of 1, i.e.,. At that point is a square root of.
We can check whether is a -th root of 1 by squaring it times and check whether it is 1. If it is, then we do not need to do anything, the same choice of and works. But if it is not, must be -1.
To find a new pair of and, we can multiply by a factor, to be determined. Then must be multiplied by a factor to keep. So we need to find a factor so that is a -th root of 1, or equivalently is a -th root of -1.
The trick here is to make use of, the known non-residue. The Euler's criterion applied to shown above says that is a -th root of -1. So by squaring repeatedly, we have access to a sequence of -th root of -1. We can select the right one to serve as. With a little bit of variable maintenance and trivial case compression, the algorithm below emerges naturally.

The algorithm

Operations and comparisons on elements of the multiplicative group of integers modulo p are implicitly mod p.
Inputs:
Outputs:
Algorithm:
  1. By factoring out powers of 2, find Q and S such that with Q odd
  2. Search for a z in which is a quadratic non-residue
  3. * Half of the elements in the set will be quadratic non-residues
  4. * Candidates can be tested with Euler's criterion or by finding the Jacobi symbol
  5. Let
  6. :
  7. Loop:
  8. * If t = 0, return r = 0
  9. * If t = 1, return r = R
  10. * Otherwise, use repeated squaring to find the least i, 0 < i < M, such that
  11. * Let, and set
  12. *:
Once you have solved the congruence with r the second solution is. 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.
For primes such that p ≡ 3, this problem has possible solutions. If these satisfy, they are the only solutions. If not,, n is a quadratic non-residue, and there are no solutions.

Proof

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.

Order of ''t''

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.

Example

Solving the congruence r2 ≡ 5. 41 is prime as required and 41 ≡ 1. 5 is a quadratic residue by Euler's criterion: .
  1. so,
  2. Find a value for z:
  3. *, so 2 is a quadratic residue by Euler's criterion.
  4. *, so 3 is a quadratic nonresidue: set
  5. Set
  6. *
  7. *
  8. *
  9. *
  10. Loop:
  11. * First iteration:
  12. **, so we're not finished
  13. **, so
  14. **
  15. **
  16. **
  17. **
  18. **
  19. * Second iteration:
  20. **, so we're still not finished
  21. ** so
  22. **
  23. **
  24. **
  25. **
  26. **
  27. * Third iteration:
  28. **, and we are finished; return
Indeed, 282 ≡ 5 and 2 ≡ 132 ≡ 5. So the algorithm yields the two solutions to our congruence.

Speed of the algorithm

The Tonelli–Shanks algorithm requires
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 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 .
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 .
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.

Uses

The Tonelli–Shanks algorithm can 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.

Generalizations

Tonelli–Shanks can be generalized to any cyclic group and to kth roots for arbitrary integer k, in particular to taking the kth root of an element of a finite field.
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.
  1. Factor out powers of 2 from p − 1, defining Q and S as: with Q odd.
  2. Let
  3. Find from the table such that and set
  4. return R.

    Tonelli's algorithm will work on mod p^k

According to Dickson's "Theory of Numbers"

A. Tonelli gave an explicit formula for the roots of

The Dickson reference shows the following formula for the square root of.
Noting that and noting that then
To take another example: and
Dickson also attributes the following equation to Tonelli:
Using and using the modulus of the math follows:
First, find the modular square root mod which can be done by the regular Tonelli algorithm:
And applying Tonelli's equation :
Dickson's reference clearly shows that Tonelli's algorithm works on moduli of.