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(a, b) 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 Iterationsschritt 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 a
b gilt. Bei der Berechnung etwa von ggt(35, 98) lautet die erste Zeile des Iterationsschemas
| 35 | : | 98 | = | 0 | Rest | 35 |
Die weiteren Iterationsschritte 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:
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:
