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 Euklidzur Person beschrieben.

Der erweiterte euklidische Algorithmus berechnet zusätzlich noch eine Darstellung von ggt(a, b) als ganzzahlige Linearkombination von a und b.

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.

abqr
98 : 35 = 2 Rest 28
35:28=1Rest7
28:7=4Rest0
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 agrößer gleichb 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 Element natürliche Zahlen0, b Element natürliche Zahlen 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 Zahlen0, b Element natürliche Zahlen. Dann gilt

ggt(a, b)  =  ggt(b, a mod b)

Beweis:  Beweis zeigen

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 natürliche Zahlen0
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.

 

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.

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

Lemma von Bézout

Der folgende Satz ist als Lemma von Bézoutzur Person bekannt.

Satz:  (Lemma von Bézout)

Seien a, b Element natürliche Zahlen0. Der größte gemeinsame Teiler ggt(a, b) lässt sich als ganzzahlige Linear­kombination 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

ai+1 = bi ui+1 = si vi+1 = ti
bi+1 = ai – qi·bi si+1 = ui – qi·si ti+1 = vi – qi·ti

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

a0 = a u0 = 1 v0 = 0
b0 = b s0 = 0 t0 = 1

Erweiterter euklidischer Algorithmus

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, 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

 

Rekursive Version

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·vb

Damit haben wir eine Darstellung von g als ganzzahlige Linearkombination von a und b gefunden.

Wir haben diese Darstellung zurückgeführt auf die Darstellung 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 extendedGcd(a, b):
    if b==0:
        return a, 1, 0
    else:
        g, u, v = extendedGcd(b, a%b)
        q=a//b
        return g, v, u-q*v

 

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

extendedGcd a 0 = (a, 1, 0)
extendedGcd a b = (g, v, u-q*v)
    where (g, u, v) = extendedGcd b (a `mod` b)
          q = a `div` b

 

 

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

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 erweiterten euklidischen Algorithmus und andere zahlen­theoretische Algorithmen finden Sie auch in meinem Buch.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortier­algorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Chinesischer Restsatz]   oder   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 12.02.2001   Updated: 27.05.2014
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik