Tonelli–Shanks algorithm

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

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=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 $R=n^{\frac {Q+1}{2}}\mod p$.
4. Let $V=W^{Q}\mod p$.
   1. Loop:
   2. Find the smallest i, $0\leq i\leq n-1$, such that $(R^{2}n^{-1})^{2^{s-i-1}}\equiv 1\mod p$. This can be done efficiently by starting with $R^{2}n^{-1}$ and squaring (mod p) until the result is 1.
   3. If $i=0$, return R.
   4. Otherwise, let $R'=RV^{2^{s-i-1}}(modp)$ and repeat the loop with R' as the new R.

Uses

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

External links

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