erweiterter Euklidischer Algorithmus

Was ist der erweiterte Euklidische Algorithmus?

Der erweiterte Euklidische Algorithmus beruht auf dem folgenden Satz (Bachet de Meziriac)! Seien a, b ∈ Z, nicht beide gleich 0. Dann gibt es ganze Zahlen s, t mit ggT(a, b) = sa+tb

Der erweiterte euklidische Algorithmus besteht nun darin, ausgehend von der vorletzten Zeile, diese Rechenschritte „von unten nach oben“ in der folgenden Weise aufzurollen, indem die einzelnen Zeilen nach den Resten aufgelöst und diese nacheinander eingesetzt werden

Sind a und m zwei teilerfremde positive ganze Zahlen, so kann eine erweiterte Version dieses Algorithmus verwendet werden, um die „modulare Inverse von a mod m„, d.h. jene (eindeutig bestimmte) positive Zahl b < m, die die Gleichung

a*b mod m=1 erfüllt, zu berechnen

Modulare inverse ( Modulo)

Modulo zu rechnen bedeutet, nur den Rest bei einer ganzzahligen Division zu betrachten

Wenn ich 9 modulo 3 berechne –> 9:3=3, 0 Rest ==> 0

Wenn ich 9 modulo 4 berechne –> 9:4=2, 1 Rest ==> 1

usw…

Beispiel 1

a = 16, b = 13, wir suchen jene Zahl c, sodass 13.c mod 16 = 1
(wir gehen zunächst noch mit der „normalen“ modularen Division vor).

  13*2 mod 16 = 10
  13*3 mod 16 =  7
  13*4 mod 16 =  4
  13*5 mod 16 =  1

Antwort: c = 5

Beispiel 2

Berechnet wird der größte gemeinsame Teiler ggt(ab) der Zahlen a = 98 und b = 35.

a b q r
98  : 35  = 2  Rest 28
35 : 28 = 1 Rest 7
28 : 7 = 4 Rest 0
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.


Wir betrachten nun einmal noch ein letztes Beispiel damit Ihr auch das richtige Gefühl für die Rechnung bekommt. Zu der Vorgabe der Zahlen 99 und 78 produziert der einfache euklidische Algorithmus die Folge von Divisionen mit Rest:

egin{matrix} underline{99}&=&1cdot underline{78}+underline{21} underline{78}&=&3cdot underline{21}+underline{15} underline{21}&=&1cdot underline{15}+underline{ 6} underline{15}&=&2cdot underline{ 6}+underline{ 3} underline{6}&=&2cdot underline{ 3}+underline{ 0} end{matrix}

3 ist ein Teiler von 6 und damit der gesuchte größte gemeinsame Teiler von 99 und 78. Nun kann man diese Gleichungen rückwärts lesen und den Rest jeweils als Differenz der beiden anderen Terme darstellen. Setzt man diese Restdarstellungen zurückgehend ineinander ein, so ergeben sich verschiedene Darstellungen des letzten Restes 3:

egin{array}{rclcl} underline{ 3}&=&underline{15}-2cdot underline{ 6} &=&underline{15}-2cdot (underline{21}-1cdot underline{15})&=&3cdotunderline{15}-2cdot underline{21} &=&3cdot(underline{78}-3cdot underline{21})-2cdot underline{21}&=&3cdotunderline{78}-11cdot underline{21} &=&3cdotunderline{78}-11cdot (underline{99}-1cdot underline{78})&=&14cdot underline{78}-11cdot underline{99} end{array}