# Tonelli–Shanks algorithm

The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2n (mod p), 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.[1]

An equivalent, but slightly more redundant version of this algorithm was developed by Alberto Tonelli[2][3] 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.[4]

According to Dickson,[3] Tonelli's algorithm takes modular square roots of ${\displaystyle x^{2}{\bmod {p^{\lambda }}}}$, of powers of primes and not just primes.

## Core ideas

Given a non-zero ${\displaystyle n}$ and an odd prime ${\displaystyle p}$, Euler's criterion tells us that ${\displaystyle n}$ has a square root (i.e., ${\displaystyle n}$ is a quadratic residue) if and only if:

${\displaystyle n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$.

In contrast, if a number ${\displaystyle z}$ has no square root (is a non-residue), Euler's criterion tells us that:

${\displaystyle z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

It is not hard to find such ${\displaystyle z}$, because half of the integers between 1 and ${\displaystyle p-1}$ have this property. So we assume that we have access to such a non-residue.

By (normally) dividing by 2 repeatedly, we can write ${\displaystyle p-1}$ as ${\displaystyle Q2^{S}}$, where ${\displaystyle Q}$ is odd. Note that if we try

${\displaystyle R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}}$,

then ${\displaystyle R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}}$. If ${\displaystyle t\equiv n^{Q}\equiv 1{\pmod {p}}}$, then ${\displaystyle R}$ is a square root of ${\displaystyle n}$. Otherwise, for ${\displaystyle M=S}$, we have ${\displaystyle R}$ and ${\displaystyle t}$ satisfying:

• ${\displaystyle R^{2}\equiv nt{\pmod {p}}}$; and
• ${\displaystyle t}$ is a ${\displaystyle 2^{M-1}}$-th root of 1 (because ${\displaystyle t^{2^{M-1}}=t^{2^{S-1}}\equiv n^{Q2^{S-1}}=n^{\frac {p-1}{2}}}$).

If, given a choice of ${\displaystyle R}$ and ${\displaystyle t}$ for a particular ${\displaystyle M}$ satisfying the above (where ${\displaystyle R}$ is not a square root of ${\displaystyle n}$), we can easily calculate another ${\displaystyle R}$ and ${\displaystyle t}$ for ${\displaystyle M-1}$ such that the above relations hold, then we can repeat this until ${\displaystyle t}$ becomes a ${\displaystyle 2^{0}}$-th root of 1, i.e., ${\displaystyle t=1}$. At that point ${\displaystyle R}$ is a square root of ${\displaystyle n}$.

We can check whether ${\displaystyle t}$ is a ${\displaystyle 2^{M-2}}$-th root of 1 by squaring it ${\displaystyle M-2}$ times and check whether it is 1. If it is, then we do not need to do anything, the same choice of ${\displaystyle R}$ and ${\displaystyle t}$ works. But if it is not, ${\displaystyle t^{2^{M-2}}}$ must be -1 (because squaring it gives 1, and there can only be two square roots 1 and -1 of 1 modulo ${\displaystyle p}$).

To find a new pair of ${\displaystyle R}$ and ${\displaystyle t}$, we can multiply ${\displaystyle R}$ by a factor ${\displaystyle b}$, to be determined. Then ${\displaystyle t}$ must be multiplied by a factor ${\displaystyle b^{2}}$ to keep ${\displaystyle R^{2}\equiv nt{\pmod {p}}}$. So we need to find a factor ${\displaystyle b^{2}}$ so that ${\displaystyle tb^{2}}$ is a ${\displaystyle 2^{M-2}}$-th root of 1, or equivalently ${\displaystyle b^{2}}$ is a ${\displaystyle 2^{M-2}}$-th root of -1.

The trick here is to make use of ${\displaystyle z}$, the known non-residue. The Euler's criterion applied to ${\displaystyle z}$ shown above says that ${\displaystyle z^{Q}}$ is a ${\displaystyle 2^{S-1}}$-th root of -1. So by squaring ${\displaystyle z^{Q}}$ repeatedly, we have access to a sequence of ${\displaystyle 2^{i}}$-th root of -1. We can select the right one to serve as ${\displaystyle b}$. 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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ are implicitly mod p.

Inputs:

• p, a prime
• n, an element of ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ 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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ such that r2 = n

Algorithm:

1. By factoring out powers of 2, find Q and S such that ${\displaystyle p-1}$=${\displaystyle Q2^{S}}$ with Q odd
2. Search for a z in ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ which is a quadratic non-residue
3. Let
{\displaystyle {\begin{aligned}M&\leftarrow S\\c&\leftarrow z^{Q}\\t&\leftarrow n^{Q}\\R&\leftarrow n^{\frac {Q+1}{2}}\end{aligned}}}
4. Loop:
• If t = 0, return r = 0
• If t = 1, return r = R
• Otherwise, use repeated squaring to find the least i, 0 < i < M, such that ${\displaystyle t^{2^{i}}=1}$
• Let ${\displaystyle b\leftarrow c^{2^{M-i-1}}}$, and set
{\displaystyle {\begin{aligned}M&\leftarrow i\\c&\leftarrow b^{2}\\t&\leftarrow tb^{2}\\R&\leftarrow Rb\end{aligned}}}

Once you have solved the congruence with r the second solution is ${\displaystyle -r{\pmod {p}}}$. If the least i such that ${\displaystyle t^{2^{i}}=1}$ 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 problem has possible solutions ${\displaystyle r=\pm n^{\frac {p+1}{4}}{\pmod {p}}}$. If these satisfy ${\displaystyle r^{2}\equiv n{\pmod {p}}}$, they are the only solutions. If not, ${\displaystyle r^{2}\equiv -n{\pmod {p}}}$, 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:

• ${\displaystyle c^{2^{M-1}}=-1}$
• ${\displaystyle t^{2^{M-1}}=1}$
• ${\displaystyle R^{2}=tn}$

Initially:

• ${\displaystyle c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1}$ (since z is a quadratic nonresidue, per Euler's criterion)
• ${\displaystyle t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1}$ (since n is a quadratic residue)
• ${\displaystyle R^{2}=n^{Q+1}=tn}$

At each iteration, with M' , c' , t' , R' the new values replacing M, c, t, R:

• ${\displaystyle c'^{2^{M'-1}}=(b^{2})^{2^{i-1}}=c^{2^{M-i}2^{i-1}}=c^{2^{M-1}}=-1}$
• ${\displaystyle t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=-1\cdot -1=1}$
• ${\displaystyle t^{2^{i-1}}=-1}$ since we have that ${\displaystyle t^{2^{i}}=1}$ but ${\displaystyle t^{2^{i-1}}\neq 1}$ (i is the least value such that ${\displaystyle t^{2^{i}}=1}$)
• ${\displaystyle b^{2^{i}}=c^{2^{M-i-1}2^{i}}=c^{2^{M-1}}=-1}$
• ${\displaystyle R'^{2}=R^{2}b^{2}=tnb^{2}=t'n}$

From ${\displaystyle t^{2^{M-1}}=1}$ 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 ${\displaystyle t^{2^{i}}=1}$. 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:

• ${\displaystyle \operatorname {ord} (c)=2^{M}}$
• ${\displaystyle \operatorname {ord} (t)|2^{M-1}}$
• ${\displaystyle R^{2}=tn}$ 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.

## Example

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: ${\displaystyle 5^{\frac {41-1}{2}}=5^{20}=1}$ (as before, operations in ${\displaystyle (\mathbb {Z} /41\mathbb {Z} )^{\times }}$ are implicitly mod 41).

1. ${\displaystyle p-1=40=5\cdot 2^{3}}$ so ${\displaystyle Q\leftarrow 5}$, ${\displaystyle S\leftarrow 3}$
2. Find a value for z:
• ${\displaystyle 2^{\frac {41-1}{2}}=1}$, so 2 is a quadratic residue by Euler's criterion.
• ${\displaystyle 3^{\frac {41-1}{2}}=40=-1}$, so 3 is a quadratic nonresidue: set ${\displaystyle z\leftarrow 3}$
3. Set
• ${\displaystyle M\leftarrow S=3}$
• ${\displaystyle c\leftarrow z^{Q}=3^{5}=38}$
• ${\displaystyle t\leftarrow n^{Q}=5^{5}=9}$
• ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2}$
4. Loop:
• First iteration:
• ${\displaystyle t\neq 1}$, so we're not finished
• ${\displaystyle t^{2^{1}}=40}$, ${\displaystyle t^{2^{2}}=1}$ so ${\displaystyle i\leftarrow 2}$
• ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$
• ${\displaystyle M\leftarrow i=2}$
• ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$
• ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$
• ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$
• Second iteration:
• ${\displaystyle t\neq 1}$, so we're still not finished
• ${\displaystyle t^{2^{1}}=1}$ so ${\displaystyle i\leftarrow 1}$
• ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$
• ${\displaystyle M\leftarrow i=1}$
• ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$
• ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$
• ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$
• Third iteration:
• ${\displaystyle t=1}$, and we are finished; return ${\displaystyle r=R=28}$

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))

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

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\leftarrow n^{\frac {Q+1}{2}},t\leftarrow 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.

### Tonelli's algorithm will work on mod p^k

According to Dickson's "Theory of Numbers"[3]

A. Tonelli[9] gave an explicit formula for the roots of ${\displaystyle x^{2}=c({\bmod {p^{\lambda }}})}$[3]

The Dickson reference shows the following formula for the square root of ${\displaystyle x^{2}{\bmod {p^{y}}}}$.

when ${\displaystyle p=4*7+1}$, or ${\displaystyle s=2}$(s must be 2 for this equation) and ${\displaystyle A=7}$ such that ${\displaystyle 29=2^{2}*7+1}$
for ${\displaystyle x^{2}{\bmod {p^{\lambda }}}\equiv c}$ then
${\displaystyle x{\bmod {p^{\lambda }}}\equiv \pm (c^{A}+3)^{\beta }*c^{(\beta +1)/2}}$ where ${\displaystyle \beta \equiv a*p^{\lambda -1}}$

Noting that ${\displaystyle 23^{2}{\bmod {29^{3}}}\equiv 529}$ and noting that ${\displaystyle \beta =7*29^{2}}$ then

${\displaystyle (529^{7}+3)^{7*29^{2}}*529^{(7*29^{2}+1)/2}{\bmod {29^{3}}}\equiv 24366\equiv -23}$

To take another example: ${\displaystyle 2333^{2}{\bmod {29^{3}}}\equiv 4142}$ and

${\displaystyle (4142^{7}+3)^{7*29^{2}}*4142^{(7*29^{2}+1)/2}{\bmod {29^{3}}}\equiv 2333}$

Dickson also attributes the following equation to Tonelli:

${\displaystyle X{\bmod {p^{y}}}\equiv x^{p^{y-1}}*c^{(p^{y}-2p^{y-1}+1)/2}}$ where ${\displaystyle X^{2}{\bmod {p^{y}}}\equiv c}$ and ${\displaystyle x^{2}{\bmod {p}}\equiv c}$;

Using ${\displaystyle p=23}$ and using the modulus of ${\displaystyle p^{3}}$ the math follows:

${\displaystyle 1115^{2}{\bmod {23^{3}}}=2191}$

First, find the modular square root mod ${\displaystyle p}$ which can be done by the regular Tonelli algorithm:

${\displaystyle 1115^{2}{\bmod {23}}\equiv 6}$ and thus ${\displaystyle {\sqrt {6}}{\bmod {23}}\equiv 11}$

And applying Tonelli's equation (see above):

${\displaystyle 11^{23^{2}}*2191^{(23^{3}-2*23^{2}+1)/2}{\bmod {23^{3}}}\equiv 1115}$

Dickson's reference[3] clearly shows that Tonelli's algorithm works on moduli of ${\displaystyle p^{\lambda }}$.

## Notes

1. ^ Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.
2. ^ Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger; Ulrich Hertrampf (24 May 2016). Discrete Algebraic Methods: Arithmetic, Cryptography, Automata and Groups. De Gruyter. pp. 163–165. ISBN 978-3-11-041632-9.
3. Leonard Eugene Dickson. History of the Theory of Numbers. 1. pp. 215–216.
4. ^ Daniel Shanks. Five Number-theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.
5. ^ Gonzalo Tornaria - Square roots modulo p, page 2 http://www.springerlink.com/content/xgxe68edy03la96p/fulltext.pdf
6. ^ Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80: 477–500, arXiv:0809.3413, doi:10.1090/s0025-5718-10-02356-2
7. ^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, doi:10.2307/2008811, JSTOR 2008811
8. ^ 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
9. ^ "AttiR. Accad. Lincei, Rendiconti, (5), 1, 1892, 116-120."

## References

• Ivan Niven; Herbert S. Zuckerman; Hugh L. Montgomery (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley. pp. 110–115. ISBN 0-471-62546-9.
• 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]