Tonelli–Shanks-Algorithmus

Deterministischer Algorithmus zur Berechnung einer Quadratwurzel eines gegebenen quadratischen Restes a modulo einer ungeraden Primzahl p (Finde x mit x^2 ≡ a (mod p)) durch Exponentiation und sukzessive Anpassungen unter Ausnutzung der Zerlegung p−1 = q·2^s und eines quadratischen Nichtrestes.