Tonelli–Shanks algorithm

The algorithm

(Note: All ≡ are taken to mean modulo p, unless indicated otherwise).

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 ≡ n .

1. Factor out powers of 2 from p − 1, defining Q and S as: p − 1 = Q 2 S with Q odd. Note that if S = 1 , i.e. p ≡ 3 ( mod 4 ) , then solutions are given directly by R ≡ ± n p + 1 4 .
2. Select a z such that the Legendre symbol ( z p ) = − 1 (that is, z is a quadratic non-residue modulo p), and set c ≡ z Q .
3. Let R ≡ n Q + 1 2 , t ≡ n Q , M = S .
4. Loop:
   1. If t ≡ 1 , return R.
   2. Otherwise, find the lowest i, 0 < i < M , such that t 2 i ≡ 1 ; e.g. via repeated squaring.
   3. Let b ≡ c 2 ( M − i − 1 ) , and set R ≡ R b , t ≡ t b 2 , c ≡ b 2 and M = i .

Once you have solved the congruence with R the second solution is p − R.

Example

Solving the congruence x 2 ≡ 10 ( mod 13 ) . It is clear that 13 is odd, and since 10 13 − 1 2 = 10 6 ≡ 1 ( mod 13 ) , 10 is a quadratic residue (by Euler's criterion).

Indeed, observe that 7 2 = 49 ≡ 10 ( mod 13 ) and naturally also ( − 7 ) 2 ≡ 6 2 ≡ 10 ( mod 13 ) . So the algorithm yields two solutions to our congruence.

Proof

First write p − 1 = Q 2 S . Now write r ≡ n Q + 1 2 ( mod p ) and t ≡ n Q ( mod p ) , observing that r 2 ≡ n t ( mod p ) . This latter congruence will be true after every iteration of the algorithm's main loop. If at any point, t ≡ 1 ( mod p ) then r 2 ≡ n ( mod p ) and the algorithm terminates with R ≡ ± r ( mod p ) .

If t ≢ 1 ( mod p ) , then consider z , a quadratic non-residue of p . Let c ≡ z Q ( mod p ) . Then c 2 S ≡ ( z Q ) 2 S ≡ z 2 S Q ≡ z p − 1 ≡ 1 ( mod p ) and c 2 S − 1 ≡ z p − 1 2 ≡ − 1 ( mod p ) , which shows that the order of c is 2 S .

Similarly we have t 2 S ≡ 1 ( mod p ) , so the order of t divides 2 S . Suppose the order of t is 2 S ′ . Since n is a square modulo p , t ≡ n Q ( mod p ) is also a square, and hence S ′ ≤ S − 1 .

Now we set b ≡ c 2 S − S ′ − 1 ( mod p ) and with this r ′ ≡ b r ( mod p ) , c ′ ≡ b 2 ( mod p ) and t ′ ≡ c ′ t ( mod p ) . As before, r ′ 2 ≡ n t ′ ( mod p ) holds; however with this construction both t and c ′ have order 2 S ′ . This implies that t ′ has order 2 S ″ with S ″ < S ′ .

If S ″ = 0 then t ′ ≡ 1 ( mod p ) , and the algorithm stops, returning R ≡ ± r ′ ( mod p ) . Else, we restart the loop with analogous definitions of b ′ , r ″ , c ″ and t ″ until we arrive at an S ( j ) ′ that equals 0. Since the sequence of S is strictly decreasing the algorithm terminates.

Speed of the algorithm

The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues))

modular multiplications, where m is the number of digits in the binary representation of p and k is the number of ones in the binary representation of p . If the required quadratic nonresidue z is to be found by checking if a randomly taken number y is a quadratic nonresidue, it requires (on average) 2 computations of the Legendre symbol. The average of two computations of the Legendre symbol are explained as follows: y is a quadratic residue with chance p + 1 2 p = 1 + 1 p 2 , which is smaller than 1 but ≥ 1 2 , so we will on average need to check if a y is a quadratic residue two times.

This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus p is random, that is, if S is not particularly large with respect to the number of digits in the binary representation of p . As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) S ( S − 1 ) > 8 m + 20 . However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of F p , one may replace S ( S − 1 ) with an expression that is asymptotically bounded by O ( S log ⁡ S / log ⁡ log ⁡ S ) . Explicitly, one computes e such that c e ≡ n Q and then R ≡ c − e / 2 n ( Q + 1 ) / 2 satisfies R 2 ≡ n (note that e is a multiple of 2 because n is a quadratic residue).

The algorithm requires us to find a quadratic nonresidue z . There is no known deterministic algorithm that runs in polynomial time for finding such a z . However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue z < 2 ln 2 ⁡ p , making it possible to check every z up to that limit and find a suitable z within polynomial time. Keep in mind, however, that this is a worst-case scenario; in general, z is found in on average 2 trials as stated above.

Uses

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.

Generalizations

Tonelli–Shanks can be generalized to any cyclic group (instead of Z / p Z ∗ ) 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: p − 1 = Q 2 S with Q odd.
2. Let R ≡ n Q + 1 2 , t ≡ n Q ≡ R 2 / n
3. Find b from the table such that b 2 ≡ t and set R ≡ R / b
4. return R.