Euklidischer Algorithmus

Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen a und b. Es ist einer der ältesten bekannten Algorithmen der Welt, benannt nach dem griechischen Mathematiker Euklid, der ihn um 300 v. Chr. in seinem Werk Die Elemente angegeben hat. Das Verfahren war jedoch schon früher bekannt. Euklid nannte es antenaresis. Der Algorithmus kommt ohne die Kenntnis der Primfaktorzerlegung der Zahlen a und b aus.

Der klassische Algorithmus

Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muß (schließlich) eine Zahl übrig bleiben, die die vorangehende misst.

(Aus Euklid, Die Elemente, Herausgegeben von Clemens Thaer, Wissenschaftliche Buchgesellschaft Darmstadt, VII Buch, §2)

Das Prinzip des euklidischen Algorithmus wird auch gegenseitige Wechselwegnahme genannt. Eingangsgrößen sind zwei natürliche Zahlen a und b. Bei der Berechnung verfährt man nach Euklid wie folgt:

• 1. setze m = a; n = b
• 2. ist m < n, so vertausche m und n
• 3. berechne r = m - n
• 4. setze m = n, n = r
• 5. ist r ≠ 0 fahre fort mit Schritt 2

Nach Ablauf des Verfahrens hat man mit m den ggT von a und b gefunden.

Wie im Zitat oben angegeben formulierte Euklid das Problem seinerzeit geometrisch, er suchte nach einem gemeinsamen "Maß" für die Längen zweier Linien. Euklid löste das Problem, indem er wiederholt die kleinere der beiden Längen von der größeren abzog.

Ist die Differenz von a und b sehr groß, sind unter Umständen sehr viele Subtraktionsschritte notwendig. Heutzutage werden die Schritte 2 und 3 deshalb in der Regel dadurch ersetzt, dass man, an Stelle der Differenz von m und n, für r den Rest bei der Division von m durch n nimmt.

Ein weiterer Vorteil dieser Variante ist, dass man sie auf beliebige euklidische Ringe (zum Beispiel Polynomringe, siehe Ringtheorie) übertragen kann, in denen der klassische Algorithmus nicht funktioniert.

Beispiel

Möchte man die den ggT von 1071 und 1029 berechnen, so erhält man der Reihe nach für m, n und r:

Der ggT ist damit 21.

Der binäre euklidische Algorithmus

Ein Problem bei der Umsetzung des euklidischen Algorithmus auf Computer ist Division, die unter Umständen einen hohen Rechenaufwand bedeutet. Hier ist deshalb der binäre euklidische Algorithmus besonders geeignet. Er verwendet nur Subtraktion und die im Dualsystem besonders einfach durchzuführende Division durch 2.

• 1. setze m = a; n = b
• 2. dividiere m und n durch 2 solange, bis eine der beiden Zahlen ungerade ist. Die Zahl der notwendigen Divisionsschritte sei k. Falls n gerade ist, vertausche m und n.
• 3. dividiere m durch 2, bis m ungerade ist
• 4. ist m<n, so vertausche diese Zahlen
• 5. setze m = m - n
• 6. ist m ≠ 0, dann fahre fort mit Schritt 3.

Nach Ablauf erhält man ggT(a,b) = n·2^k.

Hinter dem binären euklidischen Algorithmus steckt die Tatsache, dass 2 kein Faktor des ggT zweier Zahlen sein kann, wenn mindestens eine der beiden ungerade ist. Aus einer geraden Zahl kann man also so lange 2 ausdividieren, bis diese ungerade wird.

Dies geschieht in Schritt 3. Wenn im Schritt 5 von einer ungeraden Zahl eine ungerade Zahl abgezogen wird - was immer der Fall ist —, ist das Ergebnis eine gerade Zahl, aus der man nun wieder 2 ausdividieren kann. Die Bitlänge der Restzahlen verringert sich so kontinuierlich.

Das einzige Problem ergibt sich bei der Eingabe zweier gerader Zahlen. Hier muss man im Voraus entsprechend oft 2 ausdivieren (Schritt 2). Die Zahl der Divisionen muss man sich merken, da diese nach Beendigung des Algorithmus wieder rückgängig gemacht werden müssen.

Laufzeitanalyse

Mit dem euklidischen Algorithmus kann man den ggT mit verhältnismäßig geringem Aufwand (im Vergleich zur Berechnung der Primfaktorzerlegung der Zahlen a und b) berechnen. Bei der Laufzeitanalyse stellt sich interessanterweise heraus, dass der schlimmste Eingabefall zwei aufeinander folgende Fibonacci-Zahlen sind. Die Laufzeit beträgt im schlimmsten Fall Θ(n), wobei n die Anzahl der Ziffern in der Eingabe ist (siehe Landau-Symbole).

Allerdings ist die Division beliebig großer Zahlen nicht O(1), also ist die tatsächliche Laufzeit O(n²).

Euklidischer Algorithmus und Kettenbruchzerlegung

Die Quotienten, die im euklidischen Algorithmus vorkommen, sind gerade die Zahlen, die in der Kettenbruchzerlegung von a/b vorkommen. Hier für das obige Beispiel mit hervorgehobenen Ziffern:

Hieraus läßt sich der Kettenbruch entwickeln:

Dieses Verfahren lässt sich auch für jede beliebige reelle Zahl r anwenden. Ist r nicht rational, so endet der Algorithmus einfach nie. Die so gewonnene Folge an Quotienten stellt dann die unendliche Kettenbruchzerlegung von r dar.

Erweiterung

Merkt man sich die Quotienten bei der Berechnung, so lässt sich damit eine Darstellung sa+tb=ggT(a,b) mit ganzen Zahlen s und t finden. Dies nennt man den erweiterten euklidischen Algorithmus. Damit lassen sich die Inversen in Restklassenringen berechnen.

Eine andere Erweiterung ist der Algorithmus, der hinter dem Quadratischen Reziprozitätsgesetz steckt. Damit lässt sich das Jacobi-Symbol effizient berechnen.

Siehe auch

kgV und ggT, Computerprogramm