Erweiterter euklidischer Algorithmus

Kernidee und Bedeutung

Der erweiterte euklidische Algorithmus ist ein Verfahren aus der Zahlentheorie. Er berechnet zu zwei natürlichen Zahlen a und b nicht nur den größten gemeinsamen Teiler ggT(a,b), sondern auch zwei ganze Zahlen s und t mit der Gleichung

ggT(a,b) = s·a + t·b.

Damit erweitert er den einfachen euklidischen Algorithmus, der nur den größten gemeinsamen Teiler bestimmt. Die Darstellung des ggT als ganzzahlige Linearkombination der Ausgangszahlen ist der zentrale Zusatznutzen.

Wichtig ist der Algorithmus besonders zur Berechnung inverser Elemente in ganzzahligen Restklassenringen. Wenn der Algorithmus das Tripel (d = ggT(a,b), s, t) liefert, dann gilt: Ist d = 1, so folgt 1 ≡ t·b (mod a). Dann ist t das multiplikative Inverse von b modulo a. Ist dagegen d ≠ 1, dann besitzt b modulo a kein Inverses.

Diese Idee ist Grundlage für die Lösung diophantischer Gleichungen und allgemeiner ganzzahliger linearer Gleichungssysteme. Außerdem ist die Bestimmung inverser Elemente wichtig für den chinesischen Restsatz. Der Algorithmus liefert auch einen konstruktiven Beweis für das Lemma von Bézout, also für eine Gleichung der Form 1 = s·a + t·b, wenn a und b teilerfremd sind.

Der Algorithmus wird meistens für ganze Zahlen beschrieben. Er kann aber in jedem Ring verwendet werden, in dem eine Division mit kleinstem Rest möglich ist. Solche Ringe heißen euklidische Ringe. Ein Beispiel ist der Polynomring in einer Variablen mit rationalen oder reellen Koeffizienten; dort kann ein eindeutig bestimmter Rest mit kleinstem Grad gefunden werden.

Iterative Berechnung

Die iterative Variante berechnet aus den gegebenen Zahlen a und b drei Zahlenfolgen r_i, s_i und t_i. Die Folge r_i enthält die Reste wie beim einfachen euklidischen Algorithmus; s_i und t_i sind die Koeffizienten, mit denen der jeweilige Rest als Linearkombination von a und b dargestellt wird.

Die Anfangswerte sind:

r_0 = a, r_1 = b s_0 = 1, s_1 = 0 t_0 = 0, t_1 = 1

Für i = 1, 2, ... wird dann berechnet:

r_{i+1} = r_{i-1} − q_i·r_i s_{i+1} = s_{i-1} − q_i·s_i t_{i+1} = t_{i-1} − q_i·t_i

Dabei ist q_i der Quotient der Division r_{i-1} : r_i, und r_{i+1} ist der zugehörige Rest. Die Berechnung endet, sobald r_{i+1} = 0 ist. Dann ist r_i der größte gemeinsame Teiler, und es gilt

r_i = a·s_i + b·t_i.

Die iterative Methode hat den Vorteil, dass die Koeffizienten s und t bereits während der normalen ggT-Berechnung mitgeführt werden. Man muss also nicht erst alle Divisionen abwarten und anschließend rückwärts einsetzen.

Rekursives Beispiel mit 99 und 78

Für die Zahlen 99 und 78 erzeugt der einfache euklidische Algorithmus zuerst die Divisionen mit Rest:

99 = 1·78 + 21 78 = 3·21 + 15 21 = 1·15 + 6 15 = 2·6 + 3 6 = 2·3 + 0

Der letzte von Null verschiedene Rest ist 3. Also ist ggT(99,78) = 3.

Um die Koeffizienten s und t zu finden, liest man die Gleichungen rückwärts und schreibt den Rest jeweils als Differenz der beiden anderen Terme:

3 = 15 − 2·6 = 15 − 2·(21 − 1·15) = 3·15 − 2·21 = 3·(78 − 3·21) − 2·21 = 3·78 − 11·21 = 3·78 − 11·(99 − 1·78) = 14·78 − 11·99

Damit ist der größte gemeinsame Teiler als ganzzahlige Linearkombination der Ausgangszahlen dargestellt:

3 = −11·99 + 14·78.

Die gleiche Idee kann auch schrittweise während der Divisionen verwendet werden. Dann wird jeder Rest sofort als Linearkombination von 99 und 78 dargestellt, zum Beispiel 21 = 1·99 − 1·78, 15 = −3·99 + 4·78, 6 = 4·99 − 5·78 und schließlich 3 = −11·99 + 14·78.

Tabellenmethode

Die Zwischenergebnisse können in Tabellen organisiert werden. Bei der rekursiven Tabellenmethode wird zuerst der einfache euklidische Algorithmus ausgeführt. Jede Division hat die Form a = q·b + r. Der Quotient q wird in die Zeile eingetragen; das Paar (b,r) wird in der nächsten Zeile zum neuen Paar (a,b). Das wird wiederholt, bis in der Spalte b eine 0 steht.

Dann steht der größte gemeinsame Teiler in der unteren linken Ecke der Tabelle. Im Beispiel mit 99 und 78 ist das die 3. Danach werden die Koeffizienten s und t von unten nach oben berechnet, sodass in jeder Zeile gilt:

3 = s·a + t·b.

In der letzten Zeile setzt man s = 1, weil 3·1 = 3 gilt. Da dort b = 0 ist, kann t beliebig gewählt werden; im Beispiel wird t = 0 gesetzt. Danach arbeitet man sich nach oben. Für jede darüberliegende Zeile gilt:

s = t_alt

t = s_alt − q·t_alt

Im Beispiel ergeben sich in der ersten Zeile die gesuchten Werte s = −11 und t = 14. Also gilt wieder:

3 = −11·99 + 14·78.

Für die iterative Tabellenmethode kann zusätzlich mit Hilfsvariablen u und v gearbeitet werden. In jeder neuen Zeile wird die Division a = q·b + r ausgeführt, dann werden a_neu = b und b_neu = r gesetzt. Außerdem werden u_neu = s und v_neu = t übernommen, während s_neu = u − q·s und t_neu = v − q·t berechnet werden. In jeder außer der ersten Zeile gelten dann die Beziehungen a = u·a_orig + v·b_orig und b = s·a_orig + t·b_orig.

Mathematische Grundlage und Algorithmus

Allgemein erzeugt der euklidische Algorithmus zu ganzen Zahlen a und b, oder allgemeiner zu Elementen eines euklidischen Rings, eine Folge von Quotienten q_k und eine Folge von Resten r_k. Dabei gilt r_0 = a und r_1 = b. In jedem Schritt k = 1, 2, ... gilt

r_{k−1} = q_k·r_k + r_{k+1}, |r_{k+1}| < |r_k|.

Nach endlich vielen Schritten tritt der Rest 0 auf. Der letzte von Null verschiedene Rest ist der größte gemeinsame Teiler.

Für den erweiterten Algorithmus werden zusätzlich Multiplikatoren s_k konstruiert. Sie beginnen mit s_0 = 1 und s_1 = 0 und erfüllen

r_k ≡ s_k·a (mod b).

Daraus folgt die rekursive Beziehung

s_{k−1} ≡ q_k·s_k + s_{k+1}.

Praktisch ergibt sich daraus: Man setzt k = 0, r_0 = a, r_1 = b, s_0 = 1 und s_1 = 0. Dann erhöht man k, bestimmt den ganzzahligen Quotienten q_k = r_{k−1} div r_k und setzt

r_{k+1} = r_{k−1} − q_k·r_k, s_{k+1} = s_{k−1} − q_k·s_k.

Dies wird wiederholt, bis r_{k+1} = 0 gilt. Dann gibt man r_k = ggT(a,b) und s_k zurück, wobei ggT(a,b) ≡ s_k·a (mod b) gilt.

Zusätzlich gibt es zu jedem Schritt einen Koeffizienten t_k = (r_k − s_k·a) div b; diese Division hat keinen Rest. Die Folge t_k kann mit t_0 = 0, t_1 = 1 ebenfalls explizit bestimmt werden. Am Ende gilt dann

ggT(a,b) = s_k·a + t_k·b.

Pseudocode, Programmierung und Matrizen

Eine rekursive Variante des erweiterten euklidischen Algorithmus kann so beschrieben werden: Für extended_euclid(a,b) gilt im Basisfall b = 0 die Rückgabe (a,1,0). Sonst wird zuerst extended_euclid(b, a mod b) berechnet. Wenn dieser rekursive Aufruf (d',s',t') liefert, dann ist das Ergebnis

(d,s,t) = (d', t', s' − (a div b)t').

Als mathematische Funktionsdefinition steht das in der Form:

extended_euclid(a,b) = (a,1,0), wenn b = 0,

und sonst

extended_euclid(a,b) = (d',t',s' − t'(a div b))

mit (d',s',t') = extended_euclid(b, a mod b).

Der Artikel zeigt außerdem eine C++-Implementierung der rekursiven und der iterativen Variante. Beide Funktionen erhalten a und b sowie Zeiger auf s und t. Die rekursive Funktion ruft sich mit (b, a % b) auf und setzt danach s = t1 und t = s1 − (a / b)·t1. Die iterative Funktion verwendet eine Schleife, solange b != 0 ist, berechnet q = a / b und aktualisiert a, b sowie die Koeffizienten.

Für effiziente Implementierungen kann der Algorithmus auch mit Matrizen dargestellt werden. Im Schritt k wird m_k = n_k·q_k + r_k gerechnet, danach m_{k+1} = n_k und n_{k+1} = r_k = m_k − q_k·n_k. Als Matrix lautet der Übergang:

(m_{k+1}, n_{k+1})^T = [[0,1],[1,−q_k]] · (m_k, n_k)^T.

Nach L Schritten gilt n_{L+1} = 0 und m_{L+1} = ggT(a,b). Das Produkt dieser Übergangsmatrizen verbindet also den Startvektor (a,b)^T mit (ggT(a,b),0)^T. Je nachdem, ob man das Matrixprodukt von links oder von rechts auswertet, erhält man die rekursive beziehungsweise die iterative Variante des erweiterten euklidischen Algorithmus.