Berechnungsverfahren
Euklidischer Algorithmus
Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler ggt(a, b) von zwei ganzen Zahlen a und b. Der Algorithmus wurde bereits ca. 300 v.Chr. von Euklid
beschrieben.
Euklidischer Algorithmus
Der euklidische Algorithmus verwendet ein Iterationsschema, im Folgenden an einem Beispiel dargestellt. Berechnet wird der größte gemeinsame Teiler ggt(a, b) der Zahlen a = 98 und b = 35.
| a | b | q | r | |||
|---|---|---|---|---|---|---|
| 98 | : | 35 | = | 2 | Rest | 28 |
| 35 | : | 28 | = | 1 | Rest | 7 |
| 28 | : | 7 | = | 4 | Rest | 0 |
| 7 | : | 0 |
In jedem Iterationsschritt erhält a den Wert von b aus der vorherigen Zeile sowie b den Wert von r aus der vorherigen Zeile. Die Iteration endet, wenn b = 0 gilt. Das entsprechende a ist dann das Ergebnis, also der größte gemeinsame Teiler (im obigen Beispiel die 7).
Es ist nicht erforderlich, dass zu Anfang a ≥ b gilt. Bei der Berechnung etwa von ggt(35, 98) lautet die erste Zeile des Iterationsschemas
| 35 | : | 98 | = | 0 | Rest | 35 |
Die weiteren Iterationsschritte sind dann dieselben wie bei ggt(98, 35), d.h. in der ersten Zeile werden die Zahlen automatisch vertauscht, wenn sie in falscher Reihenfolge stehen.
Korrektheit
Die Korrektheit des euklidischen Algorithmus beruht auf der Tatsache, dass jeder gemeinsame Teiler d von zwei Zahlen a ∈ ℕ0, b ∈ ℕ auch deren Differenz a – b teilt. Damit teilt d auch r = a mod b = a – q·b mit q = a div b (ganzzahlige Division). Umgekehrt gilt ebenso, dass jeder gemeinsame Teiler von b und a – q·b auch a teilt.
Damit gilt dies auch für den größten gemeinsamen Teiler von a und b, d.h. es gilt der folgende Satz.
Satz: Seien a ∈ ℕ0, b ∈ ℕ. Dann gilt
ggt(a, b) = ggt(b, a mod b)
Beweis: 
In obigem Rechenschema ist somit der größte gemeinsame Teiler der jeweiligen Werte von a und b in jeder Zeile gleich. Da ggt(a, 0) = a gilt, offenbart sich der Wert des größten gemeinsamen Teilers in der letzten Zeile, wenn b = 0 gilt.
Programm
Die Gleichung des obigen Satzes lässt sich unmittelbar für folgende rekursive Version des euklidischen Algorithmus verwenden. Ist b = 0, so liefert die Funktion das korrekte Ergebnis ggt(a, 0) = a (und insbesondere auch ggt(0, 0) = 0). Ansonsten ruft sich die Funktion rekursiv selber mit den Argumenten b und a mod b auf. Das Zeichen % steht in der Programmiersprache Python für die mod-Operation.
Funktion ggt
Eingabe:
Zahlen a, b ∈ ℕ0
Ausgabe:
Größter gemeinsamer Teiler ggt(a, b)
Methode:
if b==0:
return a
else:
return ggt(b, a%b)
Die Rekursion terminiert, da a mod b stets kleiner als b ist; das zweite Argument der Funktion wird also irgendwann 0.
Iterative Version
Die ursprüngliche iterative Version ergibt folgendes Programm. In der Programmiersprache Python ist eine gleichzeitige Wertzuweisung eines Tupels von Werten an ein Tupel von Variablen möglich.
Python
while b!=0:
a, b = b, a%b
return a
Java
{
int r;
while (b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
Zeitkomplexität
Der euklidische Algorithmus hat logarithmische Zeitkomplexität bezogen auf die Größe der Zahlen a bzw. b.
Der schlechteste Fall für die Anzahl der Schritte des euklidischen Algorithmus tritt ein, wenn a und b zwei aufeinander folgende Fibonacci-Zahlen sind. Bei Eingabe der n+1-ten und der n-ten Fibonacci-Zahl benötigt der euklidische Algorithmus n Schritte. Dies sind nur logarithmisch viele Schritte in Bezug auf die Größe der n-ten Fibonacci-Zahl, denn die Fibonacci-Zahlen steigen exponentiell an.
Eine andere Abschätzung beruht darauf, dass unter der Voraussetzung b < a gilt
a mod b < a/2
Im Iterationsschema erscheint der Wert a mod b im übernächsten Schritt an der Position von a. Der Wert an der Position von a halbiert sich also mindestens alle zwei Schritte. Damit endet die Iteration nach spätestens 2·log(a) Schritten.
Aufgaben
Aufgabe 1: Programmieren Sie die iterative Version des euklidischen Algorithmus und geben Sie dabei zusätzlich in jedem Schleifendurchlauf die Werte von a und b aus. Testen Sie Ihr Programm mit den aufeinander folgenden Fibonacci-Zahlen a=987 und b=610.
Aufgabe 2: Sie beschleunigen den euklidischen Algorithmus maximal um den Faktor 2, indem Sie anstelle des Restes r das Minimum von r und b-r verwenden.
Ersetzen Sie also beispielsweise in dem iterativen Java-Programm die Anweisung b=r; durch
Geben Sie wieder in jedem Schleifendurchlauf die Werte von a und b aus. Verwenden Sie wieder das Zahlenbeispiel a=987 und b=610.
Lösen Sie die nächste Aufgabe und überzeugen Sie sich von der Korrektheit dieser Optimierung.
Aufgabe 3: Modifzieren Sie den oben angegebenen Beweis der Korrektheit des euklidischen Algorithmus und zeigen Sie
ggt(a, b) = ggt(b, b – a mod b)
Steinscher Algorithmus
Interessant ist auch eine Variante des euklidischen Algorithmus, der steinsche Algorithmus. Der steinsche Algorithmus kommt ohne die relativ aufwendige mod-Operation aus und verwendet nur Bit-Schiebe-Operationen.
Literatur
[CLRS 01] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)
Den euklidischen Algorithmus und andere zahlentheoretische Algorithmen finden Sie auch in meinem Buch.
Weitere
Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
[Lan 18] H.W. Lang: Kryptografie für Dummies. Wiley (2018)
Und natürlich finden Sie den euklidischen Algorithmus und andere zahlentheoretische Algorithmen, die in der Kryptografie gebraucht werden, auch in meinem Kryptografie-Buch.
Weiter mit: [Erweiterter euklidischer Algorithmus] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.02.2001 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden