Shanks-Tonelli algorithm

The Shanks-Tonelli algorithm is a procedure for solving a congruence of the form $x^2\equiv n(modp)$, where $p$ is an odd prime and $n$ is a quadratic residue of $p$. In other words, it can be used to compute modular square roots.

First find positive integers $Q$ and $S$ such that $p-1=2^{S}Q$, where $Q$ is odd. Then find a quadratic nonresidue $W$ of $p$ and compute $V\equiv W^Q(modp)$. Then find an integer $n^{\prime }$ that is the multiplicative inverse of $n(modp)$ (i.e., $n{n}^{\prime }\equiv 1(modp)$).

Compute

$$R\equiv n^{\frac{Q+1}{2}}(modp)$$

and find the smallest integer $i\ge 0$ that satisfies

$${(R^2{n}^{\prime })}^{2^i}\equiv 1(modp)$$

If $i=0$, then $x=R$, and the algorithm stops. Otherwise, compute

$$R^{\prime }\equiv R{V}^{2^{(S-i-1)}}(modp)$$

and repeat the procedure for $R=R^{\prime }$.

Title	Shanks-Tonelli algorithm
Canonical name	ShanksTonelliAlgorithm
Date of creation	2013-03-22 11:55:16
Last modified on	2013-03-22 11:55:16
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	10
Author	mathcam (2727)
Entry type	Algorithm
Classification	msc 11A07
Classification	msc 11Y99