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 Iterations­schema, 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 Iterations­schritt 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 Iterations­schemas

35 : 98 = 0 Rest 35

Die weiteren Iterations­schritte 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 Programmier­sprache 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üng­liche iterative Version ergibt folgendes Programm. In Python ist eine gleich­zeitige Wert­zuweisung 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
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.

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 Iterations­verfahren 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-Wert­zuweisung 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 Linear­kombination 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 Aus­multiplizieren 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 Linear­kombination von a und b gefunden.

Wir haben diese Darstellung zurück­geführt auf die Darstellung als ganzzahlige Linear­kombination 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 Linear­kombination von b und a mod b. Hieraus werden nach obigen Überlegungen die Koeffizienten v und u-q·v der ganzzahligen Linear­kombination 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 Programmier­sprache Haskell lautet wie folgt.

extendedGcd :: Integer -> Integer -> (Integer, Integer, Integer)
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 zahlentheoretische Algorithmen finden Sie auch in meinem Buch.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Chinesischer Restsatz]   oder   up

 

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


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik