Tonelli–Shanks algorithm

(Redirected from Shanks-Tonelli 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 can take square roots of x modulo prime powers pλ apart from primes.

Core ideas

edit

Given a non-zero   and a prime   (which will always be odd), Euler's criterion tells us that   has a square root (i.e.,   is a quadratic residue) if and only if:

 .

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

 .

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

By (normally) dividing by 2 repeatedly, we can write   as  , where   is odd. Note that if we try

 ,

then  . If  , then   is a square root of  . Otherwise, for  , we have   and   satisfying:

  •  ; and
  •   is a  -th root of 1 (because  ).

If, given a choice of   and   for a particular   satisfying the above (where   is not a square root of  ), we can easily calculate another   and   for   such that the above relations hold, then we can repeat this until   becomes a  -th root of 1, i.e.,  . At that point   is a square root of  .

We can check whether   is a  -th root of 1 by squaring it   times and check whether it is 1. If it is, then we do not need to do anything, as the same choice of   and   works. But if it is not,   must be -1 (because squaring it gives 1, and there can only be two square roots 1 and -1 of 1 modulo  ).

To find a new pair of   and  , we can multiply   by a factor  , to be determined. Then   must be multiplied by a factor   to keep  . So, when   is -1, we need to find a factor   so that   is a  -th root of 1, or equivalently   is a  -th root of -1.

The trick here is to make use of  , the known non-residue. The Euler's criterion applied to   shown above says that   is a  -th root of -1. So by squaring   repeatedly, we have access to a sequence of  -th root of -1. We can select the right one to serve as  . With a little bit of variable maintenance and trivial case compression, the algorithm below emerges naturally.

The algorithm

edit

Operations and comparisons on elements of the multiplicative group of integers modulo p   are implicitly mod p.

Inputs:

  • p, a prime
  • n, an element of   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   such that r2 = n

Algorithm:

  1. By factoring out powers of 2, find Q and S such that   with Q odd
  2. Search for a z in   which is a quadratic non-residue
  3. Let
     
  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  
    • Let  , and set
       

Once you have solved the congruence with r the second solution is  . If the least i such that   is M, then no solution to the congruence exists, i.e. 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  . If these satisfy  , they are the only solutions. If not,  , n is a quadratic non-residue, and there are no solutions.

Proof

edit

We can show that at the start of each iteration of the loop the following loop invariants hold:

  •  
  •  
  •  

Initially:

  •   (since z is a quadratic nonresidue, per Euler's criterion)
  •   (since n is a quadratic residue)
  •  

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

  •  
  •  
    •   since we have that   but   (i is the least value such that  )
    •  
  •  

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

edit

We can alternately express the loop invariants using the order of the elements:

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

edit

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:   (as before, operations in   are implicitly mod 41).

  1.   so  ,  
  2. Find a value for z:
    •  , so 2 is a quadratic residue by Euler's criterion.
    •  , so 3 is a quadratic nonresidue: set  
  3. Set
    •  
    •  
    •  
    •  
  4. Loop:
    • First iteration:
      •  , so we're not finished
      •  ,   so  
      •  
      •  
      •  
      •  
      •  
    • Second iteration:
      •  , so we're still not finished
      •   so  
      •  
      •  
      •  
      •  
      •  
    • Third iteration:
      •  , and we are finished; return  

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

edit

The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues))

 

modular multiplications, where   is the number of digits in the binary representation of   and   is the number of ones in the binary representation of  . If the required quadratic nonresidue   is to be found by checking if a randomly taken number   is a quadratic nonresidue, it requires (on average)   computations of the Legendre symbol.[5] The average of two computations of the Legendre symbol are explained as follows:   is a quadratic residue with chance  , which is smaller than   but  , so we will on average need to check if a   is a quadratic residue two times.

This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus   is random, that is, if   is not particularly large with respect to the number of digits in the binary representation of  . As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if)  . However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of  , one may replace   with an expression that is asymptotically bounded by  .[6] Explicitly, one computes   such that   and then   satisfies   (note that   is a multiple of 2 because   is a quadratic residue).

The algorithm requires us to find a quadratic nonresidue  . There is no known deterministic algorithm that runs in polynomial time for finding such a  . However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue  ,[7] making it possible to check every   up to that limit and find a suitable   within polynomial time. Keep in mind, however, that this is a worst-case scenario; in general,   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 and in the sieving step of the quadratic sieve.

Generalizations

edit

Tonelli–Shanks can be generalized to any cyclic group (instead of  ) 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:   with Q odd.
  2. Let  
  3. Find   from the table such that   and set  
  4. return R.

Tonelli's algorithm will work on mod p^k

edit

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

A. Tonelli[9] gave an explicit formula for the roots of  [3]

The Dickson reference shows the following formula for the square root of  .

when  , or   (s must be 2 for this equation) and   such that  
for   then
  where  

Noting that   and noting that   then

 

To take another example:   and

 

Dickson also attributes the following equation to Tonelli:

  where   and  ;

Using   and using the modulus of   the math follows:

 

First, find the modular square root mod   which can be done by the regular Tonelli algorithm:

  and thus  

And applying Tonelli's equation (see above):

 

Dickson's reference[3] clearly shows that Tonelli's algorithm works on moduli of  .

Notes

edit
  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. ^ a b c d e Leonard Eugene Dickson (1919). History of the Theory of Numbers. Vol. 1. Washington, Carnegie Institution of Washington. 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 https://doi.org/10.1007%2F3-540-45995-2_38
  6. ^ Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80 (273): 477–500, arXiv:0809.3413, doi:10.1090/s0025-5718-10-02356-2, S2CID 13940949
  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. ^ "Accademia nazionale dei Lincei, Rome. Rendiconti, (5), 1, 1892, 116-120."

References

edit
  • 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]
  • Gonzalo Tornaria [3]