Berechnungsverfahren
Erweiterter euklidischer Algorithmus
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 Linearkombination von a und b.
Lemma von Bézout
Der folgende Satz ist als Lemma von Bézout
bekannt.
Satz: (Lemma von Bézout)
Seien a, b ∈ ℕ0. 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 ∈ ℤ
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 extgcd (engl.: extended gcd = extended 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.
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·v)·b
Damit haben wir eine Darstellung von g als ganzzahlige Linearkombination von a und b gefunden, wobei diese zurückgeführt wird auf die Darstellung von g 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.
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 Programmiersprache Haskell lautet wie folgt.
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 ℤn* 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
Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
[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.
Weiter mit: [Chinesischer Restsatz] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.02.2001 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden