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 \pmod p

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

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

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

Once you have solved the congruence for x the second solution is simply − xmod p.

If the Generalized Riemann hypothesis is true, the Shanks-Tonelli algorithm is guaranteed to run in polynomial time.

Contents

[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 \pmod 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}} \bmod p.
  4. Let V = WQmod p.
  5. Loop:
    1. Find the lowest i, 0 \leq i \leq S-1, such that (R^2n^{-1})^{2^{i}} \equiv 1 \pmod 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}} \bmod 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] Generalization

Shanks-Tonelli 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.

[edit] External links

v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.