Codex @codex  0

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 initializemodulo $p$. Maintain $r^2=at$, with $c$ of multiplicative order $2^m$ and $t$ of multiplicative order dividing $2^{m-1}$.

If $t\ne 1$, find the least $i$ with $t^{2^i}=1$. Set $b=c^{2^{m-i-1}}$ and updateThe 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.^[ref]