Shanks-Tonelli algorithm

From Wikipedia, the free encyclopedia

The Shanks-Tonelli algorithm is used within modular arithmetic to solve a congruence of the form

x^2 \equiv n \mod p

where n is a quadratic residue (mod p), and p is prime; typically, p \equiv 1 \mod 4.

When p \equiv 3 \mod 4, it is much more efficient to use the following identity: x \equiv n^{\frac{p+1}{4}} \mod p.

Shanks-Tonelli cannot be used for composite moduli, which is a problem equivalent to integer factorization.

[edit] The algorithm

Inputs: p, an odd prime. n, an integer which is a quadratic residue (mod p), meaning that the Legendre symbol (n/p) = 1.

Outputs: R, an integer satisfying R^2 \equiv n \mod p.

  1. Factor out powers of 2 from (p-1), defining Q and S as: p − 1 = Q2S.
  2. Select a W such that the Legendre symbol (W/p) = -1 (that is, W should be a quadratic non-residue modulo p).
  3. Let R = n^{\frac{Q+1}{2}} \mod p.
  4. Let V = W^Q \mod p.
  5. Loop:
    1. Find the lowest i, 0 \leq i \leq n-1, such that (R^2n^{-1})^{2^{i}} \equiv 1 \mod p. This can be done efficiently by starting with R2n − 1 and squaring (mod p) until the result is 1.
    2. If i = 0, return R.
    3. Otherwise, let R' = RV^{2^{S-i-1}} \pmod{p} and repeat the loop with R' as the new R.

[edit] Uses

Modular square roots are used in, for example, the quadratic sieve and related integer factorization algorithms.

[edit] External links