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

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

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

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

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

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

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

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

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.