Zahlentheoretische Algorithmen der Kryptografie

Erweiterter 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 erweiterte euklidische Algorithmus berechnet zusätzlich noch eine Darstellung von ggt(a, b) als ganzzahlige Linearkombination von a und b.

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.

Korrektheit

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.

Programm

Die Gleichung dieses 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 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;
}

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.

Der folgende Satz ist als Lemma von Bézout bekannt.

Satz: (Lemma von Bézout)

Seien a, b Element natürliche Zahlen ₀. Der größte gemeinsame Teiler ggt(a, b) lässt sich als ganzzahlige Linearkombination von a und b darstellen:

ggt(a, b) = u·a + v·b mit u, v Element ganze Zahlen

Die Darstellung ist nicht eindeutig; die Gleichung wird durch verschiedene Zahlenpaare u, v erfüllt.

Beispiel: Der größte gemeinsame Teiler von 16 und 6 ist 2. Er lässt sich mit u = -1 und v = 3 darstellen als

2 = -1·16 + 3·6

Beweis: Der Beweis des obigen Satzes wird konstruktiv geführt. In folgendem Schema werden zunächst a und b jeweils als ganzzahlige Linearkombination von a und b dargestellt (mit u = 1 und v = 0 sowie s = 0 und t = 1).

Durch Subtraktion des q-fachen der zweiten Zeile lässt sich auch der Rest a mod b = a – q·b als ganzzahlige Linearkombination von a und b darstellen. Hierbei ist q = a div b, also der Quotient, der sich bei ganzzahliger Division von a durch b ergibt.

`a`	=	`u` · `a`	+	`v` · `b`
`b`	=	`s` · `a`	+	`t`· `b`

`a`-`q`·`b`	=	(`u`-`q`·`s`) · `a`	+	(`v`-`q`·`t`) · `b`

Indem das Schema wie bei der iterativen Version des euklidischen Algorithmus iteriert wird, mit

`a`_i+1 = `b`_i		`u`_i+1 = `s`_i		`v`_i+1 = `t`_i
`b`_i+1 = `a`_i – `q`_i·`b`_i		`s`_i+1 = `u`_i – `q`_i·`s`_i		`t`_i+1 = `v`_i – `q`_i·`t`_i

ergibt sich einerseits der größte gemeinsame Teiler von a und b und parallel dazu seine Darstellung als ganzzahlige Linearkombination von a und b. Zu Anfang ist

`a`₀ = `a`		`u`₀ = 1		`v`₀ = 0
`b`₀ = `b`		`s`₀ = 0		`t`₀ = 1

Der erweiterte euklidische Algorithmus setzt dieses Iterationsverfahren um. Er berechnet den größten gemeinsamen Teiler g zweier Zahlen a und b und zusätzlich die Koeffizienten u und v einer Darstellung von g als ganzzahlige Linearkombination.

In Python ergibt sich die folgende Implementierung in Form der Funktion extgcd (engl.: extended gcd = extended greatest common divisor). Der Operator // bedeutet ganzzahlige Division. Wiederum wird von der Tupel-Wertzuweisung Gebrauch gemacht, und die Funktion gibt ein Tupel von Werten zurück.

def extgcd(a, b):
    u, v, s, t = 1, 0, 0, 1
    while b!=0:
        q=a//b
        a, b = b, a-q*b
        u, s = s, u-q*s
        v, t = t, v-q*t
    return a, u, v

Wegen ggt(a, b) = ggt(b, a mod b) lässt sich nach dem Lemma von Bézout der größte gemeinsame Teiler g von a und b auch als ganzzahlige Linearkombination von b und a mod b darstellen:

g = u·b + v·(a mod b)

Wir schreiben a-q·b anstelle von a mod b, wobei q = a div b ist:

g = u·b + v·(a-q·b)

Durch Ausmultiplizieren erhalten wir

g = u·b + v·a – v·q·b

und durch Ordnen

g = v·a + (u-q·v)·b

Damit haben wir eine Darstellung von g als ganzzahlige Linearkombination von a und b gefunden, wobei diese zurückgeführt wird auf die Darstellung von g als ganzzahlige Linearkombination von b und a mod b. Hieraus ergibt sich unmittelbar ein rekursiver Algorithmus.

Programm

In folgendem Programm liefert der rekursive Aufruf den größten gemeinsamen Teiler g und die Koeffizienten u und v der ganzzahligen Linearkombination von b und a mod b. Hieraus werden nach obigen Überlegungen die Koeffizienten v und u-q·v der ganzzahligen Linearkombination von a und b berechnet.

Die Rekursion endet bei b = 0. Dann ist g = a und die Darstellung von g lautet g = 1·a + 0·b.

def extgcd(a, b):
    if b==0:
        return a, 1, 0
    else:
        g, u, v = extgcd(b, a%b)
        q=a//b
        return g, v, u-q*v

Die entsprechende Implementierung in der funktionalen Programmiersprache Haskell lautet wie folgt.

extgcd :: Integer -> Integer -> (Integer, Integer, Integer)
extgcd a 0 = (a, 1, 0)
extgcd a b = (g, v, u-q*v)
    where (g, u, v) = extgcd b (a `mod` b)
          q = a `div` b

Der erweiterte euklidische Algorithmus wird für die Berechnung des inversen Elements in der Gruppe ganze Zahlen _n* sowie für die Berechnungen nach dem chinesischen Restsatz gebraucht.


[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 erweiterten 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]