Wie findet man das modulare Inverse mit dem erweiterten euklidischen Algorithmus?

Wenn GGT(a, m) = 1 (d.h. a und m sind teilerfremd), dann existiert das modulare Inverse a⁻¹ mod m und ist gleich dem Bézout-Koeffizienten s (reduziert modulo m, sodass es positiv ist).

Wie wird der Algorithmus bei RSA eingesetzt?

Bei RSA ist der private Exponent d das modulare Inverse des öffentlichen Exponenten e modulo λ(n). Der erweiterte euklidische Algorithmus berechnet effizient d = e⁻¹ mod λ(n).

∞

Erweiterter-Euklid-Rechner

GGT · Bézout-Koeffizienten · Modulares Inverses

Berechne GGT(a, b) zusammen mit den ganzen Zahlen s und t, die s·a + t·b = GGT erfüllen. Komplette Iterationstabelle und modulares Inverses, wenn teilerfremd.

Schnellbeispiele

Ganze Zahl a

Ganze Zahl b

GCD(a, b)

—

Größter gemeinsamer Teiler

Bézout s

—

s · a + t · b = GGT

Bézout t

—

s · a + t · b = GGT

Mod Inverse a⁻¹ mod b

—

Nur wenn GGT = 1

Überprüfung der Bézout-Identität

GCD(a, b) = s · a + t · b

Schritt-für-Schritt Iterationstabelle

Jede Zeile: Dividend = Quotient × Divisor + Rest. Die hervorgehobene Zeile ist diejenige, in der der Rest zuerst 0 wird — der GGT ist der Divisor in dieser Zeile.

Schritt	Dividend	Divisor	Quotient	Rest	s	t

Erklärung der Rücksubstitution

🔒

RSA-Kryptographie

Key generation via modular inverse

In RSA, to generate keys for modulus n = p × q and public exponent e, the private exponent d must satisfy e × d ≡ 1 (mod λ(n)). The Extended Euclidean Algorithm computes this modular inverse efficiently.

Example: e = 17, λ(n) = 3120
GCD(17, 3120) = 1 (coprime — inverse exists)
Extended GCD → d = 17⁻¹ mod 3120
17 × 2753 = 46801 = 15 × 3120 + 1 ≡ 1 (mod 3120)
∴ Private key d = 2753

✖

Lösen von linearen diophantischen Gleichungen

Ganzzahlige Lösungen für ax + by = c

The equation ax + by = c has integer solutions if and only if GCD(a, b) divides c. The Extended Euclidean Algorithm gives a particular solution (x₀, y₀), from which the general solution follows.

General solution (when GCD | c):
x = x₀ × (c / GCD) + k × (b / GCD)
y = y₀ × (c / GCD) − k × (a / GCD) for any integer k

🔑

Kryptographischer Schlüsselaustausch

Diffie-Hellman & ElGamal foundations

Diffie-Hellman and ElGamal rely on modular arithmetic in cyclic groups. Decryption requires computing modular inverses — for example, ElGamal decryption computes s⁻¹ mod p where s is the shared secret. The Extended Euclidean Algorithm is the standard method for this computation.

ElGamal decryption: m = c₂ × (c₁ˢ)⁻¹ mod p
Inverse computed via Extended GCD(s, p)
Since p is prime, GCD(s, p) = 1 always holds (s < p)
∴ s⁻¹ mod p always exists for prime moduli

Was ist der erweiterte euklidische Algorithmus?

Der erweiterte euklidische Algorithmus ist eine leistungsstarke Erweiterung des klassischen euklidischen Algorithmus, der vom antiken griechischen Mathematiker Euklid entdeckt wurde. Während der grundlegende Algorithmus den größten gemeinsamen Teiler (GGT) zweier ganzer Zahlen durch wiederholte Division findet, berechnet die erweiterte Version gleichzeitig zwei ganzzahlige Koeffizienten s und t — genannt Bézout-Koeffizienten.

s · a + t · b = GCD(a, b)

Diese Identität, bekannt als Bézout-Identität, garantiert, dass solche ganzzahligen Koeffizienten für jedes Paar ganzer Zahlen existieren.

Die Identität von Bézout erklärt

Das Lemma von Bézout (oder Bézout-Identität) besagt: Für beliebige ganze Zahlen a und b mit dem GGT(a, b) = d existieren ganze Zahlen s und t, sodass s · a + t · b = d.

Die Bézout-Koeffizienten sind nicht eindeutig. Wenn (s, t) ein Paar ist, dann ist (s + k · (b/d), t − k · (a/d)) ein weiteres gültiges Paar für eine beliebige ganze Zahl k.

Wie der Algorithmus Schritt für Schritt funktioniert

Der Algorithmus durchläuft dieselbe Divisionsschleife wie der Basis-GGT, verfolgt aber zwei zusätzliche Sequenzen (s_i) und (t_i), die bei jedem Schritt r_i = s_i · a + t_i · b erfüllen.

r_i+1 = r_i-1 − q_i × r_i (standard GCD step)
s_i+1 = s_i-1 − q_i × s_i
t_i+1 = t_i-1 − q_i × t_i

Ausgehend von (r₀, s₀, t₀) = (a, 1, 0) und (r₁, s₁, t₁) = (b, 0, 1) endet der Algorithmus, wenn r_i = 0.

Zeitkomplexität — Satz von Lamé

Der erweiterte euklidische Algorithmus hat die Zeitkomplexität O(log min(a, b)). Der Schlüsselsatz ist der Satz von Lamé (1844).

Im Vergleich dazu wäre eine naive Suche nach Bézout-Koeffizienten exponentiell. Die logarithmische Komplexität macht ihn sogar für die riesigen Zahlen in der modernen Kryptographie (1024–4096 Bit) praktikabel.

Modulares Inverses via erweitertem euklidischem Algorithmus

Die wichtigste Anwendung ist die Berechnung modularer Inverser. Das modulare Inverse von a modulo m existiert genau dann, wenn GGT(a, m) = 1.

Wenn GGT(a, m) = 1, liefert der Algorithmus s · a + t · m = 1. Reduziert modulo m: s · a ≡ 1 (mod m), also a⁻¹ mod m = s mod m.

Referenztabelle: GGT, Bézout s, t für gängige Paare

a	b	GCD	s (Bézout)	t (Bézout)	Verification
252	105	21	-2	5	-2×252 + 5×105 = 21 ✓
35	15	5	1	-2	1×35 + (-2)×15 = 5 ✓
17	13	1	-3	4	-3×17 + 4×13 = 1 ✓
48	18	6	-1	3	-1×48 + 3×18 = 6 ✓
100	75	25	1	-1	1×100 + (-1)×75 = 25 ✓
1071	462	21	-9	21	-9×1071 + 21×462 = 21 ✓

Anwendungen in Informatik und Kryptographie

RSA-Verschlüsselung: Die Ableitung des privaten Schlüssels erfordert die Berechnung von d = e⁻¹ mod λ(n).
Chinesischer Restsatz (CRT): Die Rekonstruktion von Lösungen erfordert bei jedem Schritt modulare Inverse.
Diffie-Hellman / ElGamal: Entschlüsselungsoperationen in diesen Schemata stützen sich auf modulare Inverse.
Lineare diophantische Gleichungen: Jede Gleichung ax + by = c mit ganzzahligen Lösungen kann mithilfe von Bézout-Koeffizienten gelöst werden.
Bruchkürzung in der modularen Arithmetik: Berechnung von a/b mod m als a × b⁻¹ mod m.
Fehlerkorrektur-Codes: Reed-Solomon- und BCH-Codes verwenden polynomielle GGTs über endlichen Körpern.

Häufig gestellte Fragen

Was ist der erweiterte euklidische Algorithmus?

Der erweiterte euklidische Algorithmus erweitert die klassische GGT-Berechnung, um auch ganzzahlige Bézout-Koeffizienten s und t zu finden, die s · a + t · b = GGT(a,b) erfüllen.

Was sind Bézout-Koeffizienten?

Bézout-Koeffizienten sind ganze Zahlen s und t, sodass s · a + t · b = GGT(a, b). Ihre Existenz wird durch die Bézout-Identität garantiert.

Wie findet man das modulare Inverse mit dem erweiterten GGT?

Wenn GGT(a, m) = 1 (a und m teilerfremd sind), führe den Algorithmus auf a und m aus, um s · a + t · m = 1 zu erhalten.

Was ist die Identität von Bézout?

Die Bézout-Identität besagt, dass für zwei beliebige ganze Zahlen a und b mit d = GGT(a, b) ganze Zahlen s und t existieren mit s · a + t · b = d.

Wann existiert das modulare Inverse nicht?

Das modulare Inverse von a modulo m existiert genau dann, wenn GGT(a, m) = 1 (a und m haben keinen gemeinsamen Teiler außer 1).

Wie wird der erweiterte GGT in der RSA-Verschlüsselung verwendet?

Bei der RSA-Schlüsselerzeugung wird der private Exponent d als d = e⁻¹ mod φ(n) mithilfe des erweiterten euklidischen Algorithmus berechnet.

Was ist die Zeitkomplexität des erweiterten euklidischen Algorithmus?

Der Algorithmus läuft in O(log min(a, b)) Zeit — genauso wie der standardmäßige euklidische Algorithmus.

Erweiterter-Euklid-Rechner

Überprüfung der Bézout-Identität

Schritt-für-Schritt Iterationstabelle

RSA-Kryptographie

Lösen von linearen diophantischen Gleichungen

Kryptographischer Schlüsselaustausch

Was ist der erweiterte euklidische Algorithmus?

Die Identität von Bézout erklärt

Wie der Algorithmus Schritt für Schritt funktioniert

Zeitkomplexität — Satz von Lamé

Modulares Inverses via erweitertem euklidischem Algorithmus

Referenztabelle: GGT, Bézout s, t für gängige Paare

Anwendungen in Informatik und Kryptographie

Häufig gestellte Fragen

Ähnliche Rechner