# Tonelli–Shanks algorithm

(Redirected from Shanks–Tonelli algorithm)

The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL 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.

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 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."[2]

## The algorithm

(Note: All $\equiv$ are taken to mean $\pmod p$, unless indicated otherwise).

Inputs: p, an odd prime. n, an integer which is a quadratic residue (mod p), meaning that the Legendre symbol $\bigl(\tfrac{n}{p}\bigr)=1$.

Outputs: R, an integer satisfying $R^2 \equiv n$.

1. Factor out powers of 2 from p − 1, defining Q and S as: $p-1 = Q2^S$ with Q odd. Note that if $S = 1$, i.e. $p \equiv 3 \pmod 4$, then solutions are given directly by $R \equiv \pm n^{\frac{p+1}{4}}$.
2. Select a z such that the Legendre symbol $\bigl(\tfrac{z}{p}\bigr)=-1$ (that is, z should be a quadratic non-residue modulo p), and set $c \equiv z^Q$.
3. Let $R \equiv n^{\frac{Q+1}{2}}, t\equiv n^Q, M = S.$
4. Loop:
1. If $t \equiv 1$, return R.
2. Otherwise, find the lowest i, $0 < i < M$, such that $t^{2^i} \equiv 1$; e.g. via repeated squaring.
3. Let $b \equiv c^{2^{M-i-1}}$, and set $R \equiv Rb, \; t \equiv tb^2, c \equiv b^2$ and $M =\; i$.

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

## Example

Solving the congruence $x^2 \equiv 10 \pmod {13}$. It is clear that $13$ is odd, and since $10^{\frac{13-1}{2}} = 10^6 \equiv 1 \pmod {13}$, 10 is a quadratic residue (by Euler's criterion).

• Step 1: Observe $p-1 = 12 = 3 \cdot 2^2$ so $Q=3$, $S=2$.
• Step 2: Take $z=2$ as the quadratic nonresidue (2 is a quadratic nonresidue since $2^{\frac{13-1}{2}} = -1 \pmod {13}$ (again, Euler's criterion)). Set $c = 2^3 \equiv 8 \pmod {13}.$
• Step 3: $R=10^2 \equiv -4, \; t\equiv 10^3 \equiv -1 \pmod {13}, M = 2.$
• Step 4: Now we start the loop: $t \not\equiv 1 \pmod {13}$ so $0 < i <\; 2$; i.e. $i = \;1.$
• Let $b \equiv 8^{2^{2-1-1}} \equiv 8 \pmod {13}$, so $b^2 \equiv 8^2 \equiv -1 \pmod {13}$.
• Set $R=-4\cdot8 \equiv 7 \pmod {13}$. Set $t \equiv -1 \cdot -1 \equiv 1 \pmod {13}$, and $M =\;1.$
• We restart the loop, and since $t \equiv 1 \pmod{13}$ we are done, returning $R\equiv7 \pmod {13}.$

Indeed, observe that $7^2 = 49 \equiv 10 \pmod {13}$ and naturally also $(-7)^2 \equiv 6^2 \equiv 10 \pmod {13}$. So the algorithm yields two solutions to our congruence.

## Proof

First write $p-1=Q2^S$. Now write $r \equiv n^{\frac{Q+1}{2}}\pmod p$ and $t \equiv n^Q \pmod p$, observing that $r^2 \equiv nt \pmod p$. This latter congruence will be true after every iteration of the algorithm's main loop. If at any point, $t \equiv 1 \pmod p$ then $r^2 \equiv n \pmod p$ and the algorithm terminates with $R \equiv \pm r \pmod p$.

If $t \not\equiv 1 \pmod p$, then consider $z$, a quadratic non-residue of $p$. Let $c \equiv z^Q \pmod p$. Then $c^{2^S} \equiv (z^Q)^{2^S} \equiv z^{2^SQ}\equiv z^{p-1} \equiv 1 \pmod p$ and $c^{2^{S-1}} \equiv z^\frac{p-1}{2}\equiv -1 \pmod p$, which shows that the order of $c$ is $2^S$.

Similarly we have $t^{2^S} \equiv 1 \pmod 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 \equiv n^Q \pmod p$ is also a square, and hence $S'\leq S-1$.

Now we set $b \equiv c^{2^{S-S'-1}} \pmod p$ and with this $r' \equiv br \pmod p$, $c' \equiv b^2 \pmod p$ and $t' \equiv c't \pmod p$. As before, $r'^2 \equiv nt' \pmod 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' \equiv 1 \pmod p$, and the algorithm stops, returning $R \equiv \pm r' \pmod 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))

$2m+2k+\frac{S(S-1)}{4} +\frac{1}{2^{S-1}} - 9$

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.[3] The average of two computations of the Legendre symbol are explained as follows: $y$ is a quadratic residue with chance $\frac{\frac{p+1}{2}}{p} = \frac{1 + \frac{1}{p}}{2}$, which is smaller than $1$ but $\geq \frac{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$. Cipolla's algorithm works better than Tonelli–Shanks if (and only if) $S(S-1) > 8m + 20$.

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}$,[4] 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 $\mathbb{Z}/p\mathbb{Z}^*$) and to kth roots for arbitrary integer k, in particular to taking the kth root of an element of a finite field .[5]

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 speeded up as follows.

1. Factor out powers of 2 from p − 1, defining Q and S as: $p-1 = Q2^S$ with Q odd.
2. Let $R \equiv n^{\frac{Q+1}{2}}, t\equiv n^Q \equiv R^2/n$
3. Find $b$ from the table such that $b^2 \equiv t$ and set $R \equiv R/b$
4. return R.

## Notes

1. ^ Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.
2. ^ Daniel Shanks. Five Number-theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.
3. ^ Gonzalo Tornaria - Square roots modulo p, page 2 http://www.springerlink.com/content/xgxe68edy03la96p/fulltext.pdf
4. ^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation 55 (191): 355–380, JSTOR 2008811
5. ^ 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

## References

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. [1]
• Gagan Tara Nanda - Mathematics 115: The RESSOL Algorithm [2]