Der erweiterte euklidische Algorithmus

Hintergründe zur interaktiven Flash-Animation
RSA-Verschlüsselung


Der euklidische Algorithmus ist ein Verfahren, um den größten gemeinsamen Teiler zweier positiver ganzer Zahlen zu berechnen. Sind a und m zwei teilerfremde positive ganze Zahlen, so kann eine erweiterte Version dieses Algorithmus verwendet werden, um die "Inverse von a modulo m", d.h. jene (eindeutig bestimmte) positive Zahl b < m, die die Gleichung

ab mod m  =  1

erfüllt, zu berechnen. Wir führen anhand eines Beispiels vor, wie das Verfahren funktioniert:

Wir wollen die Inverse von 5 modulo 48 berechnen. (Sie tritt auf, wenn in der Animation p = 5, q = 13 und a = 5 gewählt wird). Dazu schreiben wir zunächst den euklidischen Algorithmus auf, so als wollten wir den größten gemeinsamen Teiler dieser beiden Zahlen ermitteln. Da 5 und 48 teilerfremd sind, wissen wir natürlich, dass dabei ggT(48, 5) = 1 herauskommen muss:


Der erweiterte euklidische Algorithmus besteht nun darin, ausgehend von der vorletzten Zeite, 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:


Beachte, dass dabei zwar alle aufretenden Klammern ausmultipliziert, nicht aber alle Produkte ausmultipliziert werden! Damit ist gezeigt, dass

2 · 48 - 19 · 5  =  1

gilt, woraus

-19 · 5 mod 48  =  1

folgt. Nun haben wir die gesuchte Inverse schon fast gefunden. Da sie positiv und kleiner als 48 sein soll, addieren wir auf der linken Seite noch 48 · 5 (was auf der rechten Seite nichts ändert, da wir modulo 48 rechnen) und erhalten

29 · 5 mod 48  =  1.

Unser Resultat lautet daher:

5 -1 mod 48  =  29.


Dieser Algorithmus macht es möglich, modulare Inverse mit Hilfe elektronischer Tools auch dann sehr schnell zu berechnen, wenn die beteiligten Zahlen groß sind.



Weitere Seiten zur RSA-Verschlüsselung: