Erweiterter euklidischer Algorithmus

Motivation

Der euklidische Algorithmus bestimmt den größten gemeinsamen Teiler (ggT) zweier ganzer Zahlen durch wiederholte Division mit Rest. Der erweiterte euklidische Algorithmus leistet mehr: Er liefert zusätzlich zwei ganzzahlige Koeffizienten $\lambda$ und $\mu$, mit denen sich der ggT als Linearkombination der beiden Ausgangszahlen schreiben lässt. Genau diese Koeffizienten benötigt man, um in $\mathbb{Z}_p$ ein multiplikatives Inverses zu berechnen — die Grundlage von RSA, der Lösung linearer Kongruenzen und des chinesischen Restsatzes.

Formale Definition

Für $a, b \in \mathbb{Z}$ besagt das Lemma von Bézout, dass es ganze Zahlen $\lambda, \mu$ gibt mit

Der erweiterte euklidische Algorithmus berechnet ein solches Paar $(\lambda, \mu)$ konstruktiv. Er führt die euklidische Division

iterativ aus und ersetzt $(a, b)$ in jedem Schritt durch $(b, r)$. Parallel werden die Koeffizienten über die Rekursion

mitgeführt, beginnend mit $(\lambda_0, \mu_0) = (1, 0)$ und $(\lambda_1, \mu_1) = (0, 1)$. Sobald der Rest $0$ erreicht, ist der vorletzte Wert der ggT, und die zugehörigen $\lambda, \mu$ erfüllen die Bézout-Identität.

Modulares Inverses in $\mathbb{Z}_p$

Ist $\gcd(a, p) = 1$, so folgt aus $\lambda \cdot a + \mu \cdot p = 1$ direkt

das heißt $\lambda$ (reduziert nach $[0, p)$) ist das Inverse $a^{-1}$ in $\mathbb{Z}_p$. Im Rechner findest du es, indem du $b = p$ und den Modulus $p$ setzt.

Durchgerechnetes Beispiel

Wir betrachten das Standardbeispiel $a = 252$, $b = 198$ — die Vorbelegung des Rechners oben. Die Divisionen mit Rest lauten:

Der letzte von $0$ verschiedene Rest ist $\gcd(252, 198) = 18$. Rückwärts eingesetzt erhält man die Bézout-Darstellung

also $\lambda = 4$ und $\mu = -5$. Genau diese Werte zeigt die Schritttabelle des Rechners.

Häufige Fehler

• Vorzeichen vergessen: $\lambda$ oder $\mu$ ist oft negativ. Über $\mathbb{Z}$ ist das korrekt; erst für ein Inverses in $\mathbb{Z}_p$ reduziert man nach $[0, p)$.
• Falscher Restbereich: Bei der euklidischen Division muss $0 \le r < b$ gelten. Ein negativer Rest liefert eine falsche Schrittfolge.
• Inverses ohne Teilerfremdheit: Nur wenn $\gcd(a, p) = 1$ existiert $a^{-1}$ in $\mathbb{Z}_p$. Andernfalls hat die Kongruenz $a x \equiv 1$ keine Lösung.
• $a$ und $b$ vertauscht: Der ggT bleibt gleich, doch $\lambda$ und $\mu$ tauschen ihre Rollen — achte darauf, welcher Koeffizient zu welcher Zahl gehört.