Das Fotonexus-Wiki befindet sich im Testbetrieb.

Aus Fotonexus.

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.^[1]

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)

Euklid berechnete den größten gemeinsamen Teiler, indem er nach einem gemeinsamen „Maß“ für die Längen zweier Linien suchte. Dazu zog er wiederholt die kleinere der beiden Längen von der größeren ab.

Ist die Differenz von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n

, für Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r

den Rest bei der Division von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m
durch Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \leftarrow
a - b
4          sonst b Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b=r_0
deren größter gemeinsamer Teiler bestimmt werden soll.

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a = q_1 \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.

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r_0 = q_2 \cdot r_1 + r_2

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r_1 = q_3 \cdot r_2 + r_3

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \vdots

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r_{n-1} = q_{n+1} \cdot r_n + 0

Der Divisor Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r_n der letzten Division ist dann der größte gemeinsame Teiler.

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \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:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1071 = 1 \cdot 1029 + 42

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1029 = 24 \cdot 42 + 21

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 42 = 2 \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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \leftarrow
a mod b
3      a Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \leftarrow
b
4      b Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \leftarrow
h
5  return a

Funktionsweise

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

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(q \cdot b + r, b) = \operatorname{ggT}(b, r)

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{a}{b}

vorkommen. Hier für das obige Beispiel mit hervorgehobenen Ziffern:

Hieraus lässt sich der Kettenbruch entwickeln:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{1071}{1029} = \mathbf{1}+ \frac{42}{1029} = \mathbf{1}+ \frac{1}{\frac{1029}{42}} = \mathbf{1}+ \frac{1}{\mathbf{24}+ \frac{21}{42}} = \mathbf{1}+ \frac{1}{\mathbf{24}+ \frac{1}{\mathbf{2}}} = [1; 24, 2]

.

Dieses Verfahren lässt sich auch für jede beliebige reelle Zahl Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r

anwenden. Ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r
nicht rational, so endet der Algorithmus einfach nie. Die so gewonnene Folge an Quotienten stellt dann die unendliche Kettenbruchzerlegung von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 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 Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f = x^4 + x^3 + x + 1

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g = x^2 - 1
gestaltet sich beispielsweise folgendermaßen:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): x^4 + x^3 + x + 1 = (x^2 + x + 1) \cdot (x^2 - 1) + (2x + 2)

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): x^2 - 1 = \Big(\frac12x - \frac12\Big) \cdot (2x + 2) + 0

Damit ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 2x+2

der größte gemeinsame Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g

.

Polynome mit Koeffizienten aus einem faktoriellen Ring

Wir halten einen faktoriellen Ring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R

fest und betrachten Polynome aus dem Polynomring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R[x]

, also Polynome in einer Variablen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): x

mit Koeffizienten aus Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R

. Im Spezialfall Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R = k[y] , wobei Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k

ein Körper sei, erhalten wir so den Ring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k[x,y]
der Polynome in zwei Variablen über Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k

.

In Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R[x]

ist Division mit Rest nicht mehr allgemein durchführbar. Seien z.B. Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f = x^2 + 1
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g = 2x + 1
in Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \mathbb{Z}[x]

. Polynomdivision in Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \mathbb{Q}[x]

liefert den Quotienten Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{1}{2}x-\frac{1}{4}

, der nicht in Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \mathbb{Z}[x]

liegt. Wir können allerdings eine Pseudodivision wie folgt definieren: Seien Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g
Polynome aus Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R[x]
mit Grad Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d_f
bzw. Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d_g

, sei Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g_0

der Leitkoeffizient des Polynoms Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g

, und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \delta := d_f - d_g . Dann gibt es Polynome Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): q,r \in R[x] , so dass

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g_0^{\delta + 1}f = qg + r,

wobei wieder Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r

von geringerem Grad ist als Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g

. Durch wiederholte Durchführung der Pseudodivision lässt sich der ggT von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g
bestimmen, allerdings ist das Verfahren in der Praxis ineffizient, da die Faktoren Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g_0^{\delta+1}
die Koeffizienten der Zwischenergebnisse exponentiell anwachsen lassen. Um das zu vermeiden kann nach jedem Schritt der Inhalt des Rests Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): r
entfernt werden, was allerdings wiederum ggT-Berechnungen in Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 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

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \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