Tonelli-Shanks Algorithm
Tonelli-Shanks berechnet Quadratwurzeln quadratischer Reste modulo einer Primzahl p: die Lösungen x von x^2≡n (mod p).
Zweck
Modulare Quadratwurzeln für Primzahlmoduln berechnen, genutzt in der Punktkompression elliptischer Kurven und der Zahlentheorie.
Mechanismus
Für p=2 oder p≡3 (mod 4) gibt es eine direkte Lösung. Allgemein schreibt man p-1=2^s*q, findet ein quadratisches Nichtrest z, setzt c=z^q und passt iterativ an, bis der Exponent auf 1 fällt. Komplexität O(s^2 log p).
Anwendungsfälle
- Punktdekompression elliptischer Kurven
- Modulare Quadratwurzeln
- Zahlentheoretische Algorithmen