Extended Euclidean Algorithm
Der erweiterte euklidische Algorithmus berechnet gcd(a,b) und findet zugleich die Bézout-Koeffizienten x, y mit ax+by=gcd(a,b).
Zweck
Modulare Inverse berechnen und lineare diophantische Gleichungen lösen; ein Grundwerkzeug der Zahlentheorie und Kryptografie.
Mechanismus
Er führt die Koeffizienten beim Rückwärtslauf durch den euklidischen Algorithmus mit: gcd(a,b)=gcd(b, a mod b), beim Rückeinsetzen x=y_prev, y=x_prev-floor(a/b)*y_prev. Laufzeit O(log min(a,b)).
Anwendungsfälle
- Berechnung modularer Inverser
- RSA-Schlüsselerzeugung
- Lineare diophantische Gleichungen