Algorithmus-Prinzip:
Der erweiterte euklidische Algorithmus berechnet nicht nur den größten gemeinsamen Teiler ggT(a, m) zweier ganzer Zahlen a und m, sondern findet auch ganze Zahlen x und y, so dass ax + my = gcd(a, m)。
Dies ist eine Anwendung der Bézout-Identität (Bézout-Gleichung).
Algorithmusschritte:
- Euklidischer Algorithmus:Berechne ggT(a, m) mit dem Divisionsalgorithmus und notiere den Quotienten und Rest bei jedem Schritt.
- Rücksubstitution:Ab dem letzten Schritt rückwärts einsetzen, um jeden Rest als Linearkombination von a und m auszudrücken.
- Koeffizienten lösen:Schließlich die Koeffizienten x und y erhalten, die ax + my = ggT(a, m) erfüllen.
Modulares Inverses:
Wenn ggT(a, m) = 1 (d. h. a und m sind teilerfremd), existiert ein multiplikatives Inverses von a modulo m, bezeichnet als a-1 mod m. In diesem Fall ist x das modulare Inverse und erfüllt a × x ≡ 1 (mod m)。
Wenn x negativ ist, muss es auf einen positiven Wert angepasst werden: x' = x mod m.
Anwendungen:
- Kryptografie:Die Berechnung des privaten Schlüssels im RSA-Algorithmus erfordert das Finden des modularen Inversen.
- Zahlentheoretische Probleme:Lösen linearer Kongruenzen der Form ax ≡ b (mod m).
- Kombinatorik:Modulare Kombinatorik-Berechnung (Lucas-Theorem usw.)
- Wettbewerbsprogrammierung:Schnelle modulare Inversen-Berechnung zur Vermeidung von Genauigkeitsproblemen durch Division
Zeitkomplexität:
O(log min(a, m)), gleich wie der euklidische Algorithmus
Bézout-Identität:
Für beliebige ganze Zahlen a und m existieren ganze Zahlen x und y, so dass ax + my = ggT(a, m). Diese Koeffizienten x und y können effizient mit dem erweiterten euklidischen Algorithmus berechnet werden.