Erweiterter Euklidischer Algorithmus Rechner

Der Rechner für den erweiterten euklidischen Algorithmus berechnet den größten gemeinsamen Teiler (ggT) von zwei Ganzzahlen und findet die Bézout-Koeffizienten – die Ganzzahlen s und t, die die Gleichung ggT(a, b) = s·a + t·b erfüllen. Über die ggT-Berechnung hinaus bietet dieses Tool eine voll animierte Schritt-für-Schritt-Divisionstabelle, Rückwärtssubstitution und die Berechnung des modularen Inversen, was es ideal für Zahlentheorie-Kurse, Kryptographie-Studien und Wettbewerbsprogrammierung macht.

Was ist der erweiterte euklidische Algorithmus?

Der Erweiterte Euklidische Algorithmus (EEA) ist eine Erweiterung von Euklids klassischem ggT-Algorithmus. Während der Basisalgorithmus den ggT(a, b) durch sukzessive Division findet, verfolgt die erweiterte Version gleichzeitig zwei Ganzzahlsequenzen, die aufzeichnen, wie jeder Rest als Linearkombination der ursprünglichen Eingaben ausgedrückt werden kann.

Wie der Algorithmus funktioniert

Der EEA behält drei Wertepaare – (r, s, t) – durch jeden Divisionsschritt bei:

1. Initialisierung: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Jeder Schritt: Berechne den Quotienten q = ⌊rₙ₋₁ / rₙ⌋, dann aktualisiere rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Stoppen, wenn der Rest = 0 ist; der vorherige Rest ist der ggT(a, b)
4. Die entsprechenden s- und t-Werte sind die Bézout-Koeffizienten

Schritt-für-Schritt-Beispiel: ggT(252, 105)

Ergebnis: ggT(252, 105) = 21, mit der Bézout-Identität: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Probieren Sie es selbst mit dem obigen Rechner für exakte Koeffizienten aus.

Anwendungen des erweiterten euklidischen Algorithmus

1. Modulares Inverses (Kryptographie)

Die wichtigste Anwendung ist die Berechnung modularer Inverser. Wenn ggT(a, m) = 1 ist, dann erfüllt der Bézout-Koeffizient s die Bedingung:

Modulare Inverse sind essenziell in der RSA-Verschlüsselung (Berechnung des privaten Schlüsselexponenten d), beim Diffie-Hellman-Schlüsselaustausch und in der Elliptische-Kurven-Kryptographie.

2. Lösen linearer diophantischer Gleichungen

Die Gleichung ax + by = c hat genau dann ganzzahlige Lösungen, wenn der ggT(a, b) ein Teiler von c ist. Falls ja, ist eine spezielle Lösung x₀ = s·(c/d), y₀ = t·(c/d), wobei d = ggT(a, b) und s, t die Bézout-Koeffizienten sind.

3. Chinesischer Restsatz

Der EEA wird im konstruktiven Beweis und bei der Berechnung des chinesischen Restsatzes verwendet – um ein x zu finden, sodass x ≡ a₁ (mod m₁) und x ≡ a₂ (mod m₂) gilt – indem modulare Inverse der Moduli berechnet werden.

4. Kürzen von Brüchen und kgV

ggT(a, b) = 1 bestätigt, dass a/b bereits vollständig gekürzt ist. Das kleinste gemeinsame Vielfache ist kgV(a, b) = |a·b| / ggT(a, b).

Bézout-Koeffizienten sind nicht eindeutig

Die Bézout-Koeffizienten s und t sind nicht eindeutig. Wenn (s, t) eine Lösung ist, dann ist (s + k·(b/d), t − k·(a/d)) für jede Ganzzahl k ebenfalls eine Lösung, wobei d = ggT(a, b). Der EEA liefert die Lösung, bei der |s| ≤ |b/d| und |t| ≤ |a/d| gilt.

Zeitkomplexität

Der erweiterte euklidische Algorithmus läuft in O(log min(a, b)) Iterationen – genau wie der einfache euklidische Algorithmus. Nach dem Satz von Lamé übersteigt die Anzahl der Schritte niemals das 5-fache der Anzahl der Dezimalstellen der kleineren Eingabe. Dies macht ihn extrem effizient, selbst für große Ganzzahlen in kryptographischen Anwendungen.

Häufig gestellte Fragen (FAQ)

Was ist der erweiterte euklidische Algorithmus?

Der erweiterte euklidische Algorithmus erweitert den euklidischen ggT-Algorithmus, um zusätzlich die Bézout-Koeffizienten s und t zu berechnen, die ggT(a, b) = s·a + t·b erfüllen. Er verfolgt während des Divisionsprozesses, wie jeder Rest als Linearkombination von a und b ausgedrückt werden kann.

Was sind Bézout-Koeffizienten?

Bézout-Koeffizienten sind Ganzzahlen s und t, deren Existenz durch das Lemma von Bézout (ein Theorem der Zahlentheorie) garantiert wird. Sie erfüllen ggT(a, b) = s·a + t·b und werden effizient durch den erweiterten euklidischen Algorithmus berechnet. Sie werden bei der Berechnung modularer Inverser, beim Lösen diophantischer Gleichungen und beim chinesischen Restsatz verwendet.

Wie finde ich das modulare Inverse mit dem erweiterten euklidischen Algorithmus?

Wenn ggT(a, b) = 1 ist (a und b sind teilerfremd), erfüllt der Bézout-Koeffizient s die Gleichung s·a ≡ 1 (mod b). Das modulare Inverse von a mod b ist s mod b (angepasst auf einen positiven Wert). Dieser Rechner zeigt dies direkt in den Ergebnissen an.

Wann existiert das modulare Inverse nicht?

Das modulare Inverse von a modulo m existiert genau dann, wenn ggT(a, m) = 1 ist. Wenn ggT(a, m) > 1 ist, erfüllt keine Ganzzahl x die Gleichung a·x ≡ 1 (mod m).

Wie hoch ist die Zeitkomplexität des erweiterten euklidischen Algorithmus?

O(log min(a, b)) Divisionen, genau wie der Basis-euklidische Algorithmus. Nach dem Satz von Lamé ist die Anzahl der Schritte auf das 5-fache der Dezimalstellen der kleineren Eingabe begrenzt, was ihn sehr effizient macht.

Zusätzliche Ressourcen

• Erweiterter euklidischer Algorithmus - Wikipedia
• Lemma von Bézout - Wikipedia