Zahlentheoretische Algorithmen der Kryptografie

Erweiterter euklidischer Algorithmus

 aufwärts

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 Linear­kombination 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.

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

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 Linear­kombination 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 Linear­kombination 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 Linear­kombination 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 Linear­kombination.

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 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.
Weiterevertikaler Abstand Themen des Buches: Sortieren, Textsuche, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortier­algorithmen.

[Weitere Informationen]

Buch  

 

 

Weiter mit:   [Chinesischer Restsatz]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 12.02.2001   Updated: 12.10.2013
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