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.

Prinzip

Die Wurzelbestimmung wird auf wiederholte Potenzierungen und kontrollierte multiplikative Korrekturen reduziert: Schreibe p−1 = q·2^s mit q ungerade, finde einen quadratischen Nichtrest z, bilde den Anfangskandidaten a^{(q+1)/2} und korrigiere iterativ mittels Potenzen von z, um 2-adische Hindernisse zu beseitigen, bis eine tatsächliche Quadratwurzel vorliegt.

Demonstration

Beispiel: für p = 11 und a = 3 stellt der Algorithmus fest, dass 3 ein quadratischer Rest ist, wählt z = 2 als Nichtrest, schreibt p−1 = 10 = 5·2^1, berechnet den Anfangskandidaten 3^{3} ≡ 5 (mod 11) und prüft 5^2 ≡ 3, daher sind x = 5 (und 6) Quadratwurzeln; das Vorgehen verallgemeinert sich auf größere p durch dieselbe Folge von Exponentiationen und Korrekturen.

Fehlanwendung

Falsche Anwendung modulo einer zusammengesetzten Zahl oder bei p = 2, oder das Anwenden bei einem quadratischen Nichtrest a führt zum Scheitern; das Auslassen der 2-adischen Zerlegung oder die Wahl eines z, das kein Nichtrest ist, liefert falsche Resultate.

Konsequenz

Bei korrekter Anwendung liefert der Algorithmus eine echte Quadratwurzel modulo einer ungeraden Primzahl und bietet eine deterministische, praktikable Methode, die in modularen Arithmetik-Routinen (z. B. Punktdekompression auf elliptischen Kurven) eingesetzt wird.

Umkehrung

Umgekehrt kann man von einem Kandidaten x ausgehen und durch Test von x^2 mod p ein a verifizieren; die Unfähigkeit, eine Wurzel zu finden, weist—mittels Legendre-Symbol—auf deren Nichtvorhandensein hin. Im Gegensatz dazu genügt bei Primzahlen mit p ≡ 3 (mod 4) oft die direkte Potenzierung x = a^{(p+1)/4}.

Abgrenzung

Gilt nur für ungerade Primmoduli p und für Eingaben a, die quadratische Reste modulo p sind; nicht direkt anwendbar auf allgemeine zusammengesetzte Moduli und benötigt das Vorhandensein eines quadratischen Nichtrestes modulo p.

Semantische Spannung

Steht im Wettbewerb mit anderen Methoden zur Berechnung modularer Quadratwurzeln wie dem Algorithmus von Cipolla (Verwendung einer quadratischen Körpererweiterung) oder speziellen Exponenten-Abkürzungen; die Abwägungen betreffen Determinismus, Laufzeitkonstanten und Implementationsaufwand.

Synthese

Tonelli–Shanks ist ein deterministisches Verfahren, das das Problem der modularen Quadratwurzel in eine kontrollierte Folge von Exponentiationen und multiplikativen Korrekturen überführt, basierend auf der 2-adischen Zerlegung von p−1 und einem gewählten Nichtrest, und so eine Wurzel liefert, wenn eine existiert.