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
Erweiterter euklidischer Algorithmus – 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)
Sie 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 Sie
g = u·b + v·a – v·q·b
und durch Ordnen
g = v·a + (u-q·v)·b
Damit haben Sie 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 erhalten Sie unmittelbar einen rekursiven 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
Den erweiterten euklidischen Algorithmus benötigen Sie für die Berechnung des inversen Elements in der Gruppe ℤn* sowie für die Berechnungen nach dem chinesischen Restsatz.
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 23] H.W. Lang: Kryptografie für Dummies. 2. Auflage, Wiley (2023)
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: 06.04.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden