= Tonelli-Shanks algorithm
{c}
= Tonelli-Shanks
{c}
{synonym}
The <Tonelli-Shanks algorithm> finds a <square root> of a <quadratic residue> $a$ <modulo> an odd <prime number> $p$. Handle $a=0$ separately and use the <Legendre symbol> to reject a <quadratic nonresidue>. Write $p-1=2^s q$ with $q$ odd, choose a <quadratic nonresidue> $z$, and initialize
$$
c=z^q,\quad t=a^q,\quad r=a^{(q+1)/2},\quad m=s
$$
<modulo> $p$. Maintain $r^2=at$, with $c$ of <multiplicative order> $2^m$ and $t$ of <multiplicative order> dividing $2^{m-1}$.
If $t\ne1$, find the least $i$ with $t^{2^i}=1$. <Set> $b=c^{2^{m-i-1}}$ and update
$$
r\leftarrow rb,\qquad t\leftarrow tb^2,\qquad c\leftarrow b^2,\qquad m\leftarrow i.
$$
The <multiplicative order> of $t$ decreases because its last nontrivial power and that of $b^2$ are both minus one. Thus $m$ strictly decreases. At $t=1$, the invariant gives $r^2=a$.
For $p=13,a=10,z=2$, initialization gives $(c,t,r,m)=(8,12,9,2)$. One update gives $r=7,t=1$, so the roots are $7$ and $6$ <modulo> thirteen.<Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone>[section 3.5.1, Algorithm 3.34; equivalent order-reduction formulation]{ref}
Back to article page
