Erweiterter Euklidischer Algorithmus


Erweiterter Euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler \operatorname{ggT}(a,b) zweier natürlicher Zahlen a und b noch zwei ganze Zahlen s und t, die die folgende Gleichung erfüllen

\operatorname{ggT}(a,b) = s \cdot a + t \cdot b

Der Algorithmus ist eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet.

Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die Berechnung der inversen Elemente in ganzzahligen Restklassenringen. Dies ist die Grundlage für die Lösung von diophantischen Gleichungen oder allgemeiner von ganzzahligen linearen Gleichungssystemen. Ebenso ist die Bestimmung inverser Elemente eine Grundlage für den chinesischen Restsatz, welcher wiederum Grundlage des bedeutenden Tricks der kleinen Primzahlen in der berechenbaren Algebra ist. Dabei wird eine Aufgabe in mehreren endlichen Körpern gelöst und diese Teillösungen in immer größere Restklassenringe gehoben, bis sich eine ganzzahlige Lösung ablesen lässt. Der Algorithmus liefert zudem einen konstruktiven Beweis für das Lemma von Bézout.

Inhaltsverzeichnis

Funktionsweise am Beispiel

Die am weitesten bekannte Version des euklidischen Algorithmus bezieht sich auf den Bereich der ganzen Zahlen. Jedoch kann er wortwörtlich auf jeden Ring angewandt werden, in welchem eine Division mit kleinstem Rest durchgeführt werden kann. Solche Ringe werden euklidisch genannt, ein Beispiel ist der Polynomring in einer Variablen mit rationalen oder reellen Koeffizienten. In diesem kann immer ein eindeutig bestimmter Rest mit kleinstem Grad gefunden werden.

Betrachten wir ein Beispiel. Zu der Vorgabe der Zahlen 99 und 78 produziert der einfache euklidische Algorithmus die Folge von Divisionen mit Rest:

\begin{matrix}
\underline{99}&=&1\cdot \underline{78}+\underline{21}\\
\underline{78}&=&3\cdot \underline{21}+\underline{15}\\
\underline{21}&=&1\cdot \underline{15}+\underline{\ 6}\\
\underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}\\
\underline{6}&=&2\cdot \underline{\ 3}+\underline{\ 0}
\end{matrix}

und 3 ist ein Teiler von 6 und damit der gesuchte größte gemeinsame Teiler von 99 und 78. Nun kann man diese Gleichungen rückwärts lesen und den Rest jeweils als Differenz der beiden anderen Terme darstellen. Setzt man diese Restdarstellungen rekursiv ineinander ein, so ergeben sich verschiedene Darstellungen des letzten Restes 3:

\begin{array}{rclcl}
\underline{\ 3}&=&\underline{15}-2\cdot \underline{\ 6}\\
&=&\underline{15}-2\cdot (\underline{21}-1\cdot \underline{15})&=&3\cdot\underline{15}-2\cdot \underline{21}\\
&=&3\cdot(\underline{78}-3\cdot \underline{21})-2\cdot \underline{21}&=&3\cdot\underline{78}-11\cdot \underline{21}\\
&=&3\cdot\underline{78}-11\cdot (\underline{99}-1\cdot \underline{78})&=&14\cdot \underline{78}-11\cdot \underline{99}
\end{array}

Der größte gemeinsame Teiler ist so als ganzzahlige Linearkombination der beiden Ausgangszahlen 78 und 99 dargestellt.

In der eben dargestellten Berechnungsvorschrift muss man erst den letzten Schritt des einfachen euklidischen Algorithmus abwarten, bevor die Berechnung der gesuchten Koeffizienten beginnen kann. Man kann aber auch ebenso alle anderen Reste als ganzzahlige Linearkombination von 78 und 99 darstellen und die zugehörigen Koeffizienten in jedem Schritt des einfachen euklidischen Algorithmus mit bestimmen:

\begin{array}{rclcrclcl}
\underline{99}&=&1\cdot \underline{78}+\underline{21}&\iff&
  \underline{21}&=&&&1\cdot\underline{99}-1\cdot \underline{78}\\
\underline{78}&=&3\cdot \underline{21}+\underline{15}&\iff&
  \underline{15}&=&1\cdot\underline{78}-3\cdot \underline{21}&=&-3\cdot\underline{99}+4\cdot \underline{78}\\
\underline{21}&=&1\cdot \underline{15}+\underline{\ 6}&\iff&
  \underline{\ 6}&=&1\cdot\underline{21}-1\cdot\underline{15}&=&4\cdot\underline{99}-5\cdot \underline{78}\\
\underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}&\iff&
  \underline{\ 3}&=&1\cdot\underline{15}-2\cdot \underline{\ 6}&=&-11\cdot\underline{99}+14\cdot \underline{78}
\end{array}

Tabellarische Darstellung

Rekursive Variante

Die Zwischenergebnisse beider Berechnungsmöglichkeiten lassen sich übersichtlich in Tabellen darstellen. Für die erste Variante, bei der die Folge der Divisionen mit Rest rückwärts aufgearbeitet wird, kann dies die folgende Gestalt annehmen:

a b q s t
99 78 1
78 21 3
21 15 1
15 6 2
6 3 2
3 0
a b q s t
99 78 1
78 21 3
21 15 1
15 6 2
6 3 2
3 0 1 0
a b q s t
99 78 1 -11 14
78 21 3 3 -11
21 15 1 -2 3
15 6 2 1 -2
6 3 2 0 1
3 0 1 0

Dabei wird zuerst, wie in der linken Tabelle, der einfache euklidische Algorithmus ausgeführt. Die Division mit Rest hat dabei immer die Form a=q·b+r, wobei q und r bestimmt werden. q wird in der Zeile vermerkt, das Paar (b,r) wird an die Stelle des Paars (a,b) in der nächsten Zeile eingetragen. Diesen Schritt wiederholen wir solange, bis in der Spalte von b eine Null steht.

Bis zu diesem Punkt haben wir den einfachen euklidischen Algorithmus ausgeführt und können in der linken unteren Ecke den größten gemeinsamen Teiler ablesen. In unserem Fall die Drei. Nun beginnt die Berechnung der ganzzahligen Koeffizienten s und t. In jeder Zeile soll dabei 3=s·a+t·b gelten. Dementsprechend tragen wir in der letzten Zeile s = 1 und t = 0 ein, es ergibt sich die mittlere Tabelle.

Nun arbeitet man sich von unten nach oben. Für das s nimmt man das t der darunterliegenden Zeile. Das t berechnet sich aus dem q der jeweiligen Zeile und dem s und t der darunterliegenden Zeile.

t = s_{alt} - q \cdot t_{alt}

Für die vorletzte Zeile ergibt sich so s = 0 und t = 1 - 2 \cdot 0 = 1, darüber dann s = 1 und t = 0 - 2 \cdot 1 = -2, usw.

Diesen Schritt wiederholen wir solange, bis die Tabelle ausgefüllt ist. Es ergibt sich die rechte Tabelle. Die Einträge für s und t in der ersten Zeile sind die gesuchten Werte. Der größte gemeinsame Teiler findet sich, wie schon erwähnt, in der unteren linken Ecke. Für das Beispiel gilt damit

3 = -11 \cdot 99 + 14 \cdot 78

Induktive Variante

Gegeben sind wieder die Werte 99 und 78:

Wie sich aus dem Beispiel ablesen lässt, hängt der aktuelle Rechenschritt von den Zwischenergebnissen der zwei vorhergehenden Rechenschritte ab. Dem kann Rechnung getragen werden, indem bei der Initialisierung eine Hilfszeile vorangestellt wird. Weiter werden, der Übersicht halber, Hilfsvariablen u und v mit einer eigenen Spalte eingefügt.

a b q u s v t
0 99 0 0 1 0 0
99 78 1 1 0 0 1
a b q u s v t
0 99 0 0 1 0 0
99 78 1 1 0 0 1
78 21 3 0 1 1 -1
21 15 1 1 -3 -1 4
15 6 2 -3 4 4 -5
6 3 2 4 -11 -5 14
3 0 -11 26 14 -33

Um die jeweils nächste Zeile zu bestimmen, werden folgende Operationen ausgeführt:

  • Es wird die Division mit Rest ausgeführt, a=q\cdot b+r und aneu = b sowie bneu = r gesetzt.
  • Die neuen Werte der Hilfsvariablen werden aus der aktuellen Zeile übernommen, uneu = s und vneu = t.
  • Die neuen Koeffizienten ergeben sich durch s_{\rm neu}=u-q\cdot s und t_{\rm neu}=v-q\cdot t

Durch diese Vorschrift gelten in jeder Zeile die Beziehungen

a=u\cdot a_{\rm orig}+v\cdot b_{\rm orig} und b=s\cdot a_{\rm orig}+t\cdot b_{\rm orig},

hier mit den Ausgangswerten aorig = 99 und borig = 78. Aus den letzten zwei Zeilen liest man daher ab, dass 3 der größte gemeinsame Teiler ist und 3=-11\cdot 99+14\cdot 78 gilt.

Ist man mit dieser Methode vertraut genug, so kann man in der Tabelle die Spalten a, u und v weglassen, da diese nur bereits weiter oben stehende Einträge wiederholen. Weitere Beispiele in dieser verknappten Form sind in den folgenden Tabellen dargestellt:

k. b q s t
-1. aorig=122 1 0
0. borig=22 5 0 1
1. 12 1 1 -5
2. 10 1 -1 6
3. 2=ggT 5 2=s -11=t
4. 0
k. b q s t
-1. aorig=120 1 0
0. borig=23 5 0 1
1. 5 4 1 -5
2. 3 1 -4 21
3. 2 1 5 -26
4. 1=ggT -9=s 47=t

Allgemeine mathematische Grundlage

Der euklidische Algorithmus erzeugt zu vorgegebenen ganzen Zahlen a und b (allgemein: Elementen eines euklidischen Rings) zwei Folgen: eine Folge (qk)k von Quotienten und eine Folge (rk)k von Resten, wobei r_0=a,\;r_1=b. In jedem Schritt k=1,2,... gilt dabei

r_{k-1}=q_k\cdot r_k+r_{k+1}, | rk + 1 | < | rk | .

Nach endlich vielen Schritten ergibt sich der Rest Null.

Wir gehen nun zu Restklassen modulo b über. Es ist trivial zu sehen, dass r_0=a=1\cdot a und r_1=b=0\cdot a+1\cdot b Vielfache von a nach Hinzufügen oder Abziehen von Vielfachen von b sind. Genauer sind die Restklassen [rk]b Vielfache der Restklasse [a]b für k=0,1, und nach Rekursionsvorschrift auch für k=2,3,.... Es kann also eine Folge von Multiplikatoren (sk)k konstruiert werden, die mit s0 = 1 und s1 = 0 initialisiert ist, so dass

r_k\equiv s_k\cdot a\pmod b

gilt. Es ergibt sich die rekursive Beziehung

s_{k-1}\equiv q_k\cdot s_{k}+s_{k+1}.

Man kann diese Rekursion in folgende Abfolge von Schritten für den erweiterten euklidischen Algorithmus fassen:

  • Erhalte a und b als Eingabe.
  • Setze k=0, r_0=a,\;r_1=b, s0 = 1 und s1 = 0.
  • Wiederhole:
    • Erhöhe k um eins.
    • Bestimme den ganzzahligen Quotienten q_k=r_{k-1}\;\div\;r_{k}.
    • Setze r_{k+1}=r_{k-1}-q_k\cdot r_k und s_{k+1}=s_{k-1}-q_k\cdot s_k.
  • bis rk + 1 = 0 gilt.
  • Gib den Rest r_k=\operatorname{ggT}(a,b) und die Zahl sk mit \operatorname{ggT}(a,b)\equiv s_k\cdot a\pmod{b} zurück.

Jeder Schritt enthält implizit auch einen Multiplikator t_k=(r_k-s_k\cdot a) \div b, wobei diese Division keinen Rest lässt. Die Folge (tk)k kann auch explizit bestimmt werden, es gelten t0 = 0, t1 = 1 und

t_{k-1}\equiv q_k\cdot t_{k}+t_{k+1}.

Nach dem letzten Schritt ergibt sich nun \operatorname{ggT}(a,b)=s_k\cdot a+t_k\cdot b

Der Übersicht halber werden beim händischen Rechnen auch noch die Hilfsfolgen (ak = rk − 1)k und (bk = rk)k sowie (uk = sk − 1)k sowie (vk = tk − 1)k mitgeführt.

Algorithmische Umsetzung

Rekursive Variante

Für den erweiterten euklidischen Algorithmus existiert auch eine rekursive Variante, die durch den folgenden Pseudocode gegeben ist:[1]

a,b: zwei Zahlen für die der erweiterte euklidische Algorithmus durchgeführt wird

extended_euclid(a,b)
1  wenn b = 0
2      dann return (a,1,0)
3  (d',s',t') \leftarrow extended_euclid(b, a mod b)
4  (d,s,t) \leftarrow (d',t',s' - floor(a/b)t')
5  return (d,s,t)

Tricks zur effizienten Computerimplementierung

Darstellung mittels Matrizen

Versieht man die Variablen des euklidischen Algorithmus mit Indizes für den Iterationsschritt, so wird im Schritt k die Division mit Rest m_k=n_k\cdot q_k+r_k ausgeführt. Im Übergang zum nächsten Schritt wird \,m_{k+1}=n_k und n_{k+1}=r_k=m_k-q_k\cdot n_k gesetzt. Bildet man aus m und n einen Spaltenvektor, so hat der gesamte Schritt eine Darstellung mit Übergangsmatrix,


    \begin{pmatrix}m_{k+1}\\n_{k+1}\end{pmatrix}
  = \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_k\end{pmatrix}
    \cdot \begin{pmatrix}m_{k}\\n_{k}\end{pmatrix}
.

Terminiert der Algorithmus nach L Schritten, so gilt \,n_{L+1}=r_L=0 und daher \,m_{L+1}=n_L=\operatorname{ggT}(a,b). Setzt man die Bildungsvorschriften der Spaltenvektoren ineinander ein, so ergibt sich die Verbindung zwischen dem ersten und dem letzten Spaltenvektor durch ein Matrizenprodukt,

\begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}
  = \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_L\end{pmatrix}
    \cdot\ldots\cdot
    \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_1\end{pmatrix}
    \cdot \begin{pmatrix}a\\b\end{pmatrix}
.

Durch Multiplikation mit dem Zeilenvektor (1,0) wird die erste Zeile auf beiden Seiten extrahiert, somit gilt

\operatorname{ggT}(a,b)
  = \begin{pmatrix}1&amp;amp;0\end{pmatrix}
    \cdot
    \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_{L}\end{pmatrix}
    \cdot\ldots\cdot
    \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_1\end{pmatrix}
    \cdot \begin{pmatrix}a\\b\end{pmatrix}
.

Die verschiedenen Arten, das Matrixprodukt der letzten Identität auszurechnen, ergeben die verschiedenen Varianten des erweiterten euklidischen Algorithmus. In der klassischen Variante, in welcher die Divisionen mit Rest von der letzten beginnend ausgewertet werden, entspricht der Bildung der Matrixprodukte beginnend von links. Diese entspricht dem nachfolgenden rekursiven Algorithmus. Es wird (s1,t1) = (1,0) gesetzt und rekursiv

(s_{k+1},t_{k+1})=(s_k,t_k)\begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_{L+1-k}\end{pmatrix}, k=1,...,L

bestimmt. Am Ende gilt \,\operatorname{ggT}(a,b)=s_{L+1}a+t_{L+1}b. Es müssen aber zuerst alle Quotienten bestimmt werden, bevor der erste Rekursionsschritt ausgeführt werden kann.


Beginnt man die Produktbildung von rechts, so wird der Quotient der Division mit Rest in dem Augenblick benutzt, in dem er bestimmt wurde und kann danach vergessen werden. Dies entspricht dem am Anfang angegebenen Algorithmus, in welchem am Anfang


    \begin{pmatrix}s_1&amp;amp;t_1\\u_1&amp;amp;v_1\end{pmatrix}=I_2=\begin{pmatrix}1&amp;amp;0\\0&amp;amp;1\end{pmatrix}
festgesetzt und 
    \begin{pmatrix}s_{k+1}&amp;amp;t_{k+1}\\u_{k+1}&amp;amp;v_{k+1}\end{pmatrix}
  = \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_k\end{pmatrix}
    \cdot
    \begin{pmatrix}s_{k}&amp;amp;t_{k}\\u_{k}&amp;amp;v_{k}\end{pmatrix}
für k=1,...,L

iteriert wird. Insgesamt ergibt sich und damit


    \begin{pmatrix}s_{L+1}&amp;amp;t_{L+1}\\u_{L+1}&amp;amp;v_{L+1}\end{pmatrix}
  = \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_L\end{pmatrix}
    \cdot\ldots\cdot
    \begin{pmatrix}0&amp;amp;1\\1&amp;amp;-q_1\end{pmatrix}
.

Am Ende gilt \,\operatorname{ggT}(a,b)=s_{L+1}a+t_{L+1}b, wobei wegen der Beziehungen \,s_{L+1}=u_L und \,t_{L+1}=v_L der letzte Iterationsschritt auch weggelassen werden kann.

Quellen

  1. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Erweiterter euklidischer Algorithmus — Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen a und b noch zwei ganze Zahlen s und t, die die folgende… …   Deutsch Wikipedia

  • Erweiterter Euklid — Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen a und b noch zwei ganze Zahlen s und t, die die folgende… …   Deutsch Wikipedia

  • Euklidscher Algorithmus — Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid… …   Deutsch Wikipedia

  • RSA-Algorithmus — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… …   Deutsch Wikipedia

  • ElGamal-Algorithmus — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Elgamal-Algorithmus — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Gcd — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • Gemeinsamer Teiler — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • GgT — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • Ggt-Bereich — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia