Shanks-Tonelli algorithm
The Shanks-Tonelli algorithm is a procedure for solving a congruence of the form , where is an odd prime and is a quadratic residue
of . In other words, it can be used to compute modular square roots.
First find positive integers and such that , where is odd. Then find a quadratic nonresidue of and compute . Then find an integer that is the multiplicative inverse of (i.e., ).
Compute
and find the smallest integer that satisfies
If , then , and the algorithm stops. Otherwise, compute
and repeat the procedure for .