Zahlentheoretische Algorithmen der Kryptografie

Erweiterter euklidischer Algorithmus

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler von zwei ganzen Zahlen. Der Algorithmus wurde bereits ca. 300 v.Chr. von Euklid beschrieben.

Da ggt(a, b) = ggt(|a|, |b|) und ggt(a, 0) = a für alle a, b Element ganze Zahlen , genügt es, das Berechnungsverfahren auf Zahlen a Element natürliche Zahlen ₀ und b Element zu beschränken.

Der euklidische 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 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:

Dieser Satz bildet die Grundlage für die folgende rekursive Version des euklidischen Algorithmus. 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.

Umgeformt in eine iterative Version ergibt sich folgendes Programm. In Python ist eine gleichzeitige Wertzuweisung eines Tupels von Werten an ein Tupel von Variablen möglich.

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

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 extendedGcd (engl.: gcd = 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 extendedGcd(a, b):
    u=t=1
    v=s=0
    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

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 06]	H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006) Den erweiterten euklidischen Algorithmus und andere zahlentheoretische Algorithmen finden Sie auch in meinem Buch. Weitere Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen. [Weitere Informationen] [Bestellen]