Shanks-Tonelli algorithm

From Wikipedia, the free encyclopedia

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

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

When , it is much more efficient to use the following identity: .

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 1 The algorithm 2 Uses 3 Generalization 4 External links

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

1. Factor out powers of 2 from (p − 1), defining Q and S as: p − 1 = Q2^S.
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 .
4. Let V = W^Qmod p.
5. Loop:
   1. Find the lowest i, , such that . This can be done efficiently by starting with R²n ^{− 1} and squaring (mod p) until the result is 1.
   2. If i = 0, return R.
   3. Otherwise, let 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 ) 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

• Quadratic Sieve Algorithm - contains a description of the Shanks-Tonelli algorithm.

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.