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.

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 größer gleich b gilt. Bei der Berechnung etwa von ggt(35, 98) lautet die erste Zeile des Iterationsschemas

Rest

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.

Die Korrektheit des euklidischen Algorithmus beruht auf der Tatsache, dass jeder gemeinsame Teiler d von zwei Zahlen a Element natürliche Zahlen ₀, b Element 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 Element natürliche Zahlen ₀, b Element . 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.

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 Element

₀

Ausgabe:

Größter gemeinsamer Teiler ggt(a, b)

Methode:

def ggt(a, b):
    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

Java

def ggt(a, b):
    while b!=0:
        a, b = b, a%b
    return a

int ggt(int a, int b)
{
    int r;
    while (b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

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.

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

b=Math.min(r, b-r);

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)

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.


[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. [Weitere Informationen]

[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. [Weitere Informationen]