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 benannt, der es in seinem Werk „Die Elemente“ beschrieben hat.

Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers.

Der euklidische Algorithmus lässt sich nicht nur auf natürliche Zahlen anwenden. Vielmehr kann damit der größte gemeinsame Teiler von zwei Elementen eines jeden euklidischen Rings berechnet werden. Dazu zählen beispielsweise Polynome über einem Körper.

Historisches

---

Der euklidische Algorithmus ist der älteste bekannte nicht-triviale Algorithmus. Das Verfahren wurde von Euklid um 300 v. Chr. in seinem Werk „Die Elemente“ (Buch VII, Proposition 1 und 2) beschrieben. Er nannte es antepheiresis (Wechselwegnahme) und formulierte es als geometrisches Problem: Er suchte ein gemeinsames „Maß“ zweier Strecken. Das Verfahren wurde jedoch wahrscheinlich nicht von Euklid erfunden, sondern war schon bis zu 200 Jahre früher bekannt. Es war mit annähernder Sicherheit Eudoxos von Knidos (um 375 v. Chr.) bekannt und auch Aristoteles (um 330 v. Chr.) wies auf dieses Verfahren in seinem Werk „Topik“ (158b, 29-35) hin.Donald E. Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2, S. 334–337

Der klassische Algorithmus

---

Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (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.

Wie aus dem obigen Zitat ersichtlich 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.

Euklidischer_Algorithmus.png

Ist die Differenz von $a$ und $b$ sehr groß, sind unter Umständen sehr viele Subtraktionsschritte notwendig. Heutzutage wird in der Regel der weiter unten beschriebene Divisions-Algorithmus verwendet, bei dem die Schritte 2 und 3 dadurch ersetzt werden, 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.

Beschreibung durch Pseudocode

Der klassische Algorithmus hier in Pseudocode dargestellt:

EUCLID_OLD(a,b) 1 solange b ≠ 0 2 wenn a > b 3 dann a $\backslash leftarrow$ a - b 4 sonst b $\backslash leftarrow$ b - a 5 return a

Dieser Algorithmus kann auch in einer rekursiven Version angegeben werden: EUCLID_OLD_RECURSIVE(a,b) 1 wenn b = 0 2 dann return a 3 sonst wenn a > b 4 dann return EUCLID_OLD_RECURSIVE(a - b, b) 5 sonst return EUCLID_OLD_RECURSIVE(a, b - a)

Moderner Euklidischer Algorithmus

---

Heutzutage ersetzt man die im klassischen Algorithmus auftretenden wiederholten Subtraktionen eines Wertes jeweils durch eine einzige Division mit Rest. Der moderne euklidische Algorithmus führt nun in jedem Schritt solch eine Division mit Rest aus. Er beginnt mit den beiden Zahlen $a$ und $b=r\_0$ deren größter gemeinsamer Teiler bestimmt werden soll.

$a\; =\; q\_1\; \backslash cdot\; r\_0\; +\; r\_1$

In jedem weiteren Schritt wird mit dem Divisor und dem Rest des vorhergehenden Schritts eine erneute Division mit Rest durchgeführt. Und zwar solange bis eine Division aufgeht, das heißt der Rest Null ist.

$r\_0\; =\; q\_2\; \backslash cdot\; r\_1\; +\; r\_2$

$r\_1\; =\; q\_3\; \backslash cdot\; r\_2\; +\; r\_3$

$\backslash vdots$

$r\_\{n-1\}\; =\; q\_\{n+1\}\; \backslash cdot\; r\_n\; +\; 0$

Der Divisor $r\_n$der letzten Division ist dann der größte gemeinsame Teiler.

$\backslash operatorname\{ggT\}(a,b)\; =\; r\_n$

Da sich die Zahlen in jedem Schritt mindestens halbieren, ist das Verfahren auch bei großen Zahlen extrem schnell.

Beispiel

Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:

$1071\; =\; 1\; \backslash cdot\; 1029\; +\; 42$

$1029\; =\; 24\; \backslash cdot\; 42\; +\; 21$

$42\; =\; 2\; \backslash cdot\; 21\; +\; 0$

Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.

Beschreibung durch Pseudocode

Im Folgenden wird der moderne Euklidische Algorithmus sowohl in einer rekursiven, als auch einer iterativen Variante beschrieben. Dabei sind $a$ und $b$ jeweils die beiden Zahlen deren größter gemeinsamer Teiler berechnet werden soll.

Rekursive Variante

EUCLID(a,b) 1 wenn b = 0 2 dann return a 3 sonst return EUCLID(b, a mod b)

Iterative Variante

EUCLID(a,b) 1 solange b ≠ 0 2 h $\backslash leftarrow$ a mod b 3 a $\backslash leftarrow$ b 4 b $\backslash leftarrow$ h 5 return a

Funktionsweise

Der euklidische Algorithmus beruht auf folgenden Eigenschaften des größten gemeinsamen Teilers.

$\backslash operatorname\{ggT\}(q\; \backslash cdot\; b\; +\; r,\; b)\; =\; \backslash operatorname\{ggT\}(b,\; r)$

$\backslash operatorname\{ggT\}(a,\; 0)\; =\; a$

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. Bei aufeinander folgenden Fibonacci-Zahlen ergibt sich als Rest immer die nächst kleinere Fibonacci-Zahl. Die Anzahl der benötigten Divisionen beträgt im schlimmsten Fall Θ(log(ab)), wobei log(ab) proportional zur Anzahl der Ziffern in der Eingabe ist (siehe Landau-Symbole). Da die für die Division zweier Zahlen benötigte Zeit wiederum von der Anzahl der Ziffern der Zahlen abhängt, ergibt sich eine tatsächliche Laufzeit von O(log(ab)²).

Euklidischer Algorithmus und Kettenbruchzerlegung

---

Die Quotienten, die im euklidischen Algorithmus vorkommen, sind genau die Zahlen, die in der Kettenbruchzerlegung von $\backslash frac\{a\}\{b\}$ vorkommen. Hier für das obige Beispiel mit hervorgehobenen Ziffern:

1071	= 1	× 1029	+ 42
1029	= 24	× 42	+ 21
42	= 2	× 21	+ 0

Hieraus lässt sich der Kettenbruch entwickeln:

$\backslash frac\{1071\}\{1029\}\; =\; \backslash mathbf\{1\}+\; \backslash frac\{42\}\{1029\}\; =\; \backslash mathbf\{1\}+\; \backslash frac\{1\}\{\backslash frac\{1029\}\{42\}\}\; =\; \backslash mathbf\{1\}+\; \backslash frac\{1\}\{\backslash mathbf\{24\}+\; \backslash frac\{21\}\{42\}\}\; =\; \backslash mathbf\{1\}+\; \backslash frac\{1\}\{\backslash mathbf\{24\}+\; \backslash frac\{1\}\{\backslash mathbf\{2\}\}\}\; =24,\; 2$.

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.

Euklidischer Algorithmus für Polynome

---

Polynome in einer Variable über einem Körper bilden einen euklidischen Ring. Die Polynomdivision ist für diese Polynome also eine Division mit Rest und der euklidische Algorithmus kann genauso wie bei den ganzen Zahlen durchgeführt werden. Die Berechnung des größten gemeinsamen Teilers der Polynome $f\; =\; x^4\; +\; x^3\; +\; x\; +\; 1$ und $g\; =\; x^2\; -\; 1$ gestaltet sich beispielweise folgendermaßen:

$x^4\; +\; x^3\; +\; x\; +\; 1\; =\; (x^2\; +\; x\; +\; 1)\; \backslash cdot\; (x^2\; -\; 1)\; +\; (2x\; +\; 2)$

$x^2\; -\; 1\; =\; \backslash Big(\backslash frac12x\; -\; \backslash frac12\backslash Big)\; \backslash cdot\; (2x\; +\; 2)\; +\; 0$

Damit ist $2x+2$ der größte gemeinsame Teiler von $f$ und $g$.

Polynome mit Koeffizienten aus einem faktoriellen Ring

Wir halten einen faktoriellen Ring $R$ fest und betrachten Polynome aus dem Polynomring

In , so dass

$g\_0^\{\backslash delta\; +\; 1\}f\; =\; qg\; +\; r,$

wobei wieder $r$ von geringerem Grad ist als $g$. Durch wiederholte Durchführung der Pseudodivision lässt sich der ggT von $f$ und $g$ bestimmen, allerdings ist das Verfahren in der Praxis ineffizient, da die Faktoren $g\_0^\{\backslash delta+1\}$ die Koeffizienten der Zwischenergebnisse exponentiell anwachsen lassen. Um das zu vermeiden kann nach jedem Schritt der Inhalt des Rests $r$ entfernt werden, was allerdings wiederum ggT-Berechnungen in $R$ erfordert. Effizienter lässt sich der ggT mit dem Subresultantenverfahren berechnen.

Varianten

---

Von Josef Stein stammt der nach ihm benannte Steinsche Algorithmus bei dem auf die aufwändigen Divisionen verzichtet werden kann. Lediglich auf einem Rechner leicht durchzuführende Divisionen durch Zwei sind noch notwendig. Deshalb wird dieser Algorithmus auch Binärer Euklidischer Algorithmus genannt.

Merkt man sich die Quotienten bei der Berechnung, so lässt sich damit eine Darstellung

$\backslash operatorname\{ggT\}(a,b)\; =\; sa\; +\; tb$

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.

Quellen

---

Algorithmus | Zahlentheorie

خوارزمية إقليدس | Алгоритъм на Евклид | Algorisme d'Euclides | Euklidův algoritmus | Euclidean algorithm | Algoritmo de Euclides | Eukleideen algoritmi | Algorithme d'Euclide | Euklidészi algoritmus | Algoritma Euklidean | Algoritmo di Euclide | ユークリッドの互除法 | 유클리드 호제법 | Euklido algoritmas | Algoritme van Euclides | Algorytm Euklidesa | Algoritmo de Euclides | Алгоритм Евклида | Evklidov algoritem | Euklides algoritm | Giải thuật Euclid | 輾轉相除法