 Tonelli–Shanks algorithm

The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime. It uses the decomposition of the prime minus one into an odd part and a power of two to successively correct a candidate root.

The Tonelli–Shanks algorithm is a method used to compute square roots in finite fields, particularly useful for finding square roots of a number modulo a prime. This algorithm is significant in number theory and has applications in cryptography, especially in schemes dealing with quadratic residues.