## [Extraktion Modularer Quadratwurzeln](/de/node/62921) Definition Der Prozess, ganze Zahlen x zu finden, die x^2 ≡ a (mod n) erfüllen, wenn solche Lösungen existieren; also Quadratwurzeln in Ringen Z/nZ oder in deren lokalen Faktoren bei zusammengesetztem n zu extrahieren. ## Prinzip Prinzip Die Lösbarkeit hängt davon ab, ob a ein quadratischer Rest modulo jeder Primpotenz ist, die n teilt; für Primmodul p verwendet man Algorithmen wie Tonelli–Shanks (für ungerade p) oder direkte Prüfung für p=2; für Primpotenzen wendet man Hensel‑Lifting an; für zusammengesetzte n reduziert Faktorisierung plus chinesischer Restsatz das Problem auf Primpotenzen. ## Demonstration Demonstration Beispiel: Finde x mit x^2 ≡ 10 (mod 13). Quadrate modulo 13 zeigen 6^2 = 36 ≡ 10 und 7^2 = 49 ≡ 10, also sind x ≡ 6 und x ≡ 7 (mod 13) Lösungen. Bei zusammengesetztem n faktorisiere n, löse jede Primpotenzkongruenz und kombiniere mittels CRT, um alle Lösungen modulo n zu erhalten. ## Fehlanwendung Fehlanwendung Zu glauben, dass stets eine Quadratwurzel modulo eines zusammengesetzten Moduls existiert, ohne Quadratresiduosität an jedem Primfaktor zu prüfen, oder CRT ohne kompatible lokale Lösungen anzuwenden; Tonelli–Shanks unreflektiert anzuwenden ist ebenfalls fehlerhaft. ## Konsequenz Konsequenz Korrekte Extraktion liefert explizite Wurzelklassen, die in Primzahlerkennung, kryptographischen Protokollen (und Angriffen) und beim Heben von Lösungen auf höhere Moduli Verwendung finden. ## Umkehrung Umkehrung Die umgekehrte Sicht ist die Entscheidung der quadratischen Residuosität (ob a ein Quadrat modulo n ist) statt der Konstruktion der Wurzeln; wenn Residuosität schwer zu entscheiden ist (z. B. zusammengesetztes n ohne Faktorisierung), ist die Extraktion unpraktikabel und die Residuositätsfrage zentral. ## Abgrenzung Abgrenzung Gilt für quadratische Kongruenzen x^2 ≡ a (mod n) und hängt von der Faktorisierung von n ab; schließt allgemeine k‑te Wurzelextraktion aus, sofern nicht angepasst, und ist praktisch ohne Faktorisierung zusammengesetzter n oft nicht praktikabel. ## Semantische Spannung Semantische Spannung Spannung zwischen dem Arbeiten in Primkörpern F_p (Feld, Standardalgorithmen anwendbar) und zusammengesetzten Modulen Z/nZ (kein Feld): Ersteres erlaubt direkte algebraische Methoden, letzteres erfordert Faktorisierung und CRT oder führt zu Mehrdeutigkeiten, wenn Faktoren unbekannt sind. ## Synthese Synthese Die modulare Quadratwurzelextraktion prüft lokal die quadratische Residuosität bei Primpotenzen, berechnet lokale Wurzeln (Tonelli–Shanks, Hensel‑Lifting) und rekombiniert per Chinesischem Restsatz, um alle ganzzahligen Lösungen x modulo n zu konstruieren, sofern diese existieren.