Herr Lemma von Bezout hat herausgefunden, daß man den GGT zweier ganzer Zahlen durch eine Vielfachsummendarstellung derselbigen darstellen kann. Hört sich recht kompliziert an, wie das anscheinend mit einer Definition sein muß. Das nächste Beispiel wird den Schleier des Komplizierten aber hoffentlich lüften:
Nehmen wir mal die zwei ganzen Zahlen 5 und 3 der GGT ist folglich 1.
Nach dem Satz von Bezout gibt es nun die Zahlen x und y, so das folgendes gilt:
x * 5 + y * 3 = 1
Mit ein wenig nachdenken, findet man folgende Lösung:
5 * 5 + (-8) * 3 = 1
Mag man sich natürlich fragen, was das Ganze eigentlich soll? Nun dieser Zusammenhang wird für das Verständnis des RSA Algorithmus Grundvoraussetzung sein.
Gemäß dem obigen Beispiel gilt also folgender Satz:
Sei t = ggT(a,b),
dann gibt es ganze Zahlen s und t
für die gilt
s * a + t * b = g
Einen Spezialfall gibt es noch zu betrachten:
Seien die zwei ganzen Zahlen a und b teilerfremd,
dann gibt es ganze Zahlen s und t
für die gilt
s * a + t * b = 1
Im oben genannten Beispiel konnte die Lösung für s und t noch durch ein wenig nachdenken gefunden werden.Ist a = 3459 und b = 5648 muß man schon sehr gut nachdenken können. Den ggT können wir mit dem Satz von Euklid berechnen. Für s und t haben wir allerdings noch kein systematisches Verfahren. Aber keine Angst, auch dieses Problem haben die Mathematiker über eine Erweiterung des Satz von Euklid gelöst. Auch hier möchte ich wieder ein kleines Beispiel bringen:
Sei a = 4 und b = 19
Berechnung des ggT nach Euklid:
I. 19 = 4 * 4 + 3
II. 4 = 1 * 3 + 1 => ggT(19,4) = 1
III. 3 = 3 * 1 + 0
Berechnung von s und t nach dem erweiterten Satz von Euklid:
4 = 1 * 3 + 1
1 = 4 - 1 * 3 aus I. folgt 3 = 19 - 4 * 4
1 = 4 - 1 * (19 - 4 * 4)
1 = 5 * 4 - 1 * 19
Das Ergebnis lautet s = 5 und t = -1.
Das Verfahren beruht also darauf, daß wir nach Umstellung der vorletzten Zeile, die sich in der ggT Berechnung ergeben hat, einfach nacheinander die darüberliegenden Gleichungen einsetzen und durch die darauf folgende Ausmultiplikation das Ergebnis erhalten.