Tonelli–Shanks algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

(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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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 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[edit]

  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 
  5. ^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation 55 (191): 355–380, 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[edit]

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]

External links[edit]