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

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$ .

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}}$ .
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$ .
Let $R \equiv n^{\frac{Q+1}{2}}, t\equiv n^Q, M = S.$
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 p − R.

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: so ; i.e.
- 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$ . As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) $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 $\mathbb{F}_p$ , one may replace $S(S-1)$ with an expression that is asymptotically bounded by $O(S\log S/\log\log S)$ .^[4] Explicitly, one computes $e$ such that $c^e\equiv n^Q$ and then $R\equiv c^{-e/2} n^{(Q+1)/2}$ satisfies $R^2\equiv 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}$ ,^[5] 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 .^[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.

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

Notes

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

Niven, Ivan; Herbert S. Zuckerman, Hugh L. Montgomery (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley. ISBN 0-471-62546-9. Cite uses deprecated parameter |coauthors= (help)

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.
Gagan Tara Nanda - Mathematics 115: The RESSOL Algorithm

External links

Implementation in C# http://shankstonelli.blogspot.com/2010/12/shanks-tonelli-algorithm-in-c.html
Implementation in Python http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW ECPP test Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia - version of the Friday, November 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.