Berechnungsverfahren

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

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 extgcd (engl.: extended gcd = extended 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 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

 

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, wobei diese zurück­geführt wird auf die Darstellung von g 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 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 Programmier­sprache 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 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  
[Lan 18]H.W. Lang: Kryptografie für Dummies. Wiley (2018)

Und natürlich finden Sie den erweiterten euklidischen Algorithmus und andere zahlentheoretische Algorithmen auch in meinem Kryptografie-Buch.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Chinesischer Restsatz]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 12.02.2001   Updated: 28.07.2022
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

 

 

Master-Studiengang
Angewandte Informatik

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

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik