For , the first order bound already gives . The second supplementary law for quadratic reciprocity says that two is then a quadratic residue modulo . Euler's criterion gives , so its multiplicative order divides . Thus , further reducing the candidate factors. At , meets this bound. The restriction matters: has factor five, which is not one modulo eight.
Tonelli-Shanks algorithm Created 2026-10-20 Updated 2026-11-05
The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime number . Handle separately and use the Legendre symbol to reject a quadratic nonresidue. Write with odd, choose a quadratic nonresidue , and initialize
modulo . Maintain , with of multiplicative order and of multiplicative order dividing .
If , find the least with . Set and update
The multiplicative order of decreases because its last nontrivial power and that of are both minus one. Thus strictly decreases. At , the invariant gives .
For , initialization gives . One update gives , so the roots are and modulo thirteen.[ref]