## [Tonelli–Shanks-Algorithmus](/de/node/62002) Definition 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 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 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 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 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 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 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 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 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.