# Tonelli–Shanks 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

${\displaystyle 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 ${\displaystyle \equiv }$ are taken to mean ${\displaystyle {\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 ${\displaystyle {\bigl (}{\tfrac {n}{p}}{\bigr )}=1}$.

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

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

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

## Example

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

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

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

## Proof

First write ${\displaystyle p-1=Q2^{S}}$. Now write ${\displaystyle r\equiv n^{\frac {Q+1}{2}}{\pmod {p}}}$ and ${\displaystyle t\equiv n^{Q}{\pmod {p}}}$, observing that ${\displaystyle 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, ${\displaystyle t\equiv 1{\pmod {p}}}$ then ${\displaystyle r^{2}\equiv n{\pmod {p}}}$ and the algorithm terminates with ${\displaystyle R\equiv \pm r{\pmod {p}}}$.

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

Similarly we have ${\displaystyle t^{2^{S}}\equiv 1{\pmod {p}}}$, so the order of ${\displaystyle t}$ divides ${\displaystyle 2^{S}}$. Suppose the order of ${\displaystyle t}$ is ${\displaystyle 2^{S'}}$. Since ${\displaystyle n}$ is a square modulo ${\displaystyle p}$, ${\displaystyle t\equiv n^{Q}{\pmod {p}}}$ is also a square, and hence ${\displaystyle S'\leq S-1}$.

Now we set ${\displaystyle b\equiv c^{2^{S-S'-1}}{\pmod {p}}}$ and with this ${\displaystyle r'\equiv br{\pmod {p}}}$, ${\displaystyle c'\equiv b^{2}{\pmod {p}}}$ and ${\displaystyle t'\equiv c't{\pmod {p}}}$. As before, ${\displaystyle r'^{2}\equiv nt'{\pmod {p}}}$ holds; however with this construction both ${\displaystyle t}$ and ${\displaystyle c'}$ have order ${\displaystyle 2^{S'}}$. This implies that ${\displaystyle t'}$ has order ${\displaystyle 2^{S''}}$ with ${\displaystyle S''.

If ${\displaystyle S''=0}$ then ${\displaystyle t'\equiv 1{\pmod {p}}}$, and the algorithm stops, returning ${\displaystyle R\equiv \pm r'{\pmod {p}}}$. Else, we restart the loop with analogous definitions of ${\displaystyle b'}$, ${\displaystyle r''}$, ${\displaystyle c''}$ and ${\displaystyle t''}$ until we arrive at an ${\displaystyle 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))

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

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

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

The algorithm requires us to find a quadratic nonresidue ${\displaystyle z}$. There is no known deterministic algorithm that runs in polynomial time for finding such a ${\displaystyle z}$. However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue ${\displaystyle z<2\ln ^{2}{p}}$,[5] making it possible to check every ${\displaystyle z}$ up to that limit and find a suitable ${\displaystyle z}$ within polynomial time. Keep in mind, however, that this is a worst-case scenario; in general, ${\displaystyle 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 ${\displaystyle \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 .[6]

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: ${\displaystyle p-1=Q2^{S}}$ with Q odd.
2. Let ${\displaystyle R\equiv n^{\frac {Q+1}{2}},t\equiv n^{Q}\equiv R^{2}/n}$
3. Find ${\displaystyle b}$ from the table such that ${\displaystyle b^{2}\equiv t}$ and set ${\displaystyle 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. ^ 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
5. ^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, doi:10.2307/2008811, JSTOR 2008811
6. ^ 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]