Station - Berechnung des modularen Inversen
Naiver Berechnung des modularen Inversen
Im letzen Abschnitt wurde der folgende Baustein zur Berechnung des modularen Inversen benutzt:
def modInv(e, n):
gefunden = False
d = 1
while d <= n and not gefunden:
if (e * d) % n == 1:
gefunden = True
else:
d = d + 1
if d > n:
d = -1
return d
Der Algorithmus, der diesem Baustein zu Grunde liegt, lässt sich informell so beschreiben: Prüfe der Reihe nach alle Zahlen, ob sie die geforderte Inversen-Eigenschaft haben. Beende diesen Prozess, wenn eine solche Zahl gefunden wurde, oder n erreicht ist.
Der Baustein ist nur für kleine n-Werte praktikabel. Bei größeren n-Werten kann es vorkommen, dass die Abarbeitung der Schleife so lange dauert, dass man in der zur Verfügung stehenden Zeit zu keinem Ergebnis kommt.
Wenn man beispielsweise das modulare Inverse von b = 49 bzgl. des Moduls n = 1000010000100001000010000100001000010000100001000010000 bestimmen möchte, so benötigt ein handelsüblicher Rechner für 10 Millionen Überprüfungen derzeit mehr als 1 Sekunde. Bis zum Ergebnis a = 775517959261225265313877628572204089387832653836742449 benötigt er dann in etwa t = 77551795926122526531387762857220408938783265383 Sekunden. Das sind mehr als 1039 Jahre. Klar, dass man auf dieses Ergebnis nicht warten kann. Selbst wenn die Rechner um den Faktor 1000 schneller werden, so ist die Rechenzeit immer noch weit jenseits aller akzeptablen Grenzen.
Mit dem naiven Verfahren kann man also nicht garantieren, dass das modularen Inverse in vertretbarer Zeit berechnet werden kann.
Die Situation ändert sich nur, wenn ein besserer Algorithmus zur Berechnung des modularen Inversen gefunden wird.
Erweiterter euklidischer Algorithmus
Der euklidischer Algorithmus ist ein Standardalgorithmus zur Berechnung des größten gemeinsamen Teilers (kurz ggT) von zwei vorgegebenen natürlichen Zahlen. Dieser Algorithmus lässt sich so erweitern, dass hiermit auch modulare Inverse bestimmt werden können.
Wir betrachten zunächst ein Beispiel.
Gegeben sind die Zahlen a = 884 und b = 320.
Gesucht ist eine Darstellung der Gestalt ggT(a, b) = x*a + y*b mit zwei weiteren Zahlen x und y.
Die Berechnung erfolgt schrittweise:
(1) 884 = 2*320 + 244
244 = 884 - 2*320 = (1*884 + 0*320) - 2*(0*884 + 1*320) = 1*884 - 2*320
(2) 320 = 1*244 + 76
76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = (-1)*884 + 3*320
(3) 244 = 3*76 + 16
16 = 244 - 3*76 = (1*884 - 2*320) - 3*((-1)*884 + 3*320) = 4*884 - 11*320
(4) 76 = 4*16 + 12
12 = 76 - 4*16 = ((-1)*884 + 3*320) - 4*(4*884 - 11*320) = (-17)*884 + 47*320
(5) 16 = 1*12 + 4
4 = 16 - 1*12 = (4*884 - 11*320) - 1*((-17)*884 + 47*320) = 21*884 - 58*320
(6) 12 = 3*4 + 0
0 = 12 - 3*4 = (-17*884 + 47*320) - 3*(21*884 + -58*320) = -80*884 + 221*320
Die nummerierten Zeilen beschreiben die Berechnungsschritte des euklidischen Algorithmus.
Die darunter aufgeführten Zeilen beschreiben Umformungen, die zur Bestimmung von x und y benötigt werden.
Als Ergebnis der Berechnungen erhält man:
ggT(884, 320) = 4 = 21*884 + (- 58)*320 = x*884 + y*320
Also x = 21 und y = -58.
Exkurs Mathematik (Zahlentheorie)
Die Aussage, dass der ggT zweier Zahlen als deren Linearkombination dargestellt werden kann, ist auch als Lemma von Bezout bekannt.
Aus dem letzten Schritt des erweiterten euklidischen Algorithmus lässt sich übrigens neben dem $ggT(884,320)$ auch noch das $kgV(884,320)$ ablesen. Im obigen Fall lautet es: $80 \cdot 884=221 \cdot 320=70.720$
Für das $ggT(a,b)$ und das $kgV(a,b)$ gilt der folgende allgemeine Zusammenhang: $ggT(a,b) \cdot kgV(a,b)=a \cdot b$, wie man sich mittels der Primfaktorzerlegung der Zahlen $a$ und $b$ leicht klarmachen kann.
Im obigen Fall erhält man durch diese Formel erneut: $kgV(884,320) = \frac{884\cdot 320}{ggt(884,320)}=\frac{282.880}{4}=70.720$Implementierung des erweiterten euklidischen Algorithmus
Der folgende Python-Quelltext enthält eine Implementierung des erweiterten euklidischen Algorithmus.
Zum Mitverfolgen ist eine print-Anweisung integriert. Wenn es nur auf eine schnelle
Berechnung ankommt, sollte diese print-Anweisung entfernt (oder auskommentiert) werden.
def erweiterterEuklidischerAlgorithmus(a, b):
aalt = a
amitte = b
xalt = 1
xmitte = 0
yalt = 0
ymitte = 1
while amitte != 0:
q = aalt // amitte
aneu = aalt - q * amitte
xneu = xalt - xmitte * q
yneu = yalt - ymitte * q
xalt = xmitte
xmitte = xneu
yalt = ymitte
ymitte = yneu
aalt = amitte
amitte = aneu
print(amitte, ' = ', xmitte, ' * ', a, ' + ', ymitte, ' * ', b)
return (aalt, xalt, yalt)
Das folgende Python-Protokoll zeigt, wie man den gezeigten Baustein nutzen kann:
>>> erweiterterEuklidischerAlgorithmus(884, 320)
244 = 1 * 884 + -2 * 320
76 = -1 * 884 + 3 * 320
16 = 4 * 884 + -11 * 320
12 = -17 * 884 + 47 * 320
4 = 21 * 884 + -58 * 320
0 = -80 * 884 + 221 * 320
(4, 21, -58)
Aufgabe 1
Bestimme mit Hilfe des erweiterten euklidischen Algorithmus den größten gemeinsamen Teiler von
- 45 und 39.
- 196 und 135.
- 301 und 139.
Überprüfe deine Ergebnisse mit Hilfe der Implementierung.
Schnelle Berechnung des modularen Inversen
Aus den Ergebnissen des erweiterten euklidischen Algorithmus lässt sich durch Umformung das modulare Inverse bestimmen.
Beispiel 1: Gesucht wird das modulare Inverse von a = 41 bzgl. m = 192.
>>> erweiterterEuklidischerAlgorithmus(41, 192)
(1, 89, -19)
Umformungen:
1 = 89*41 + (-19)*192
1 - (-19)*192 = 89*41
[1 - (-19)*192]% 192 = [89*41]%192
[1 + 19*192]% 192 = [89*41]%192
1 = [89*41]%192
Ergebnis: Das modulare Inverse ist b = 89.
Beispiel 2: Gesucht wird das modulare Inverse von a = 17 bzgl. m = 192.
>>> erweiterterEuklidischerAlgorithmus(17, 192)
(1, -79, 7)
Umformungen:
1 = (-79)*17 + 7*192
1 - 7*192 = (-79)*17
1 - 7*192 + 192*17 = (-79+192)*17
1 + 10*192 = 113*17
[1 + 10*192]%192 = [113*17]%192
1 = [113*17]%192
Ergebnis: Das modulare Inverse ist b = 113.
Die in den Beispielen gezeigten Umformungen lassen sich allgemein beschreiben und liefern - zusammen mit dem erweiterten euklidischen Algorithmus ein Verfahren zur Bestimmung des modularen Inversen.
def modInv(a, m):
(ggt, x, y) = erweiterterEuklidischerAlgorithmus(a, m)
if ggt > 1:
return -1
else:
if x < 0:
x = x + m
return x
Aufgabe 2
Bestimme mit Hilfe analoger Umformungen das modulare Inverse von
- 39 bezüglich 45.
- 135 bezüglich 196.
- 139 bezüglich 301.
Überprüfe deine Ergebnisse mit Hilfe der Implementierung.
Aufgabe 3
Bestimme mit Hilfe der Implementierung das modulare Inverse von 49 bezüglich 1000010000100001000010000100001000010000100001000010000. Vergleiche mit dem naiven Ansatz.
Aufgabe 4
Beurteile abschließend die Sicherheit des Verfahrens mit modularer Multiplikation. Welche Rolle spielt hierbei der erweiterte euklidische Algorithmus?
Sicherheit des Verfahrens mit modularer Multiplikation
Aus den Ergebnissen und Überlegungen können wir jetzt die folgende Bewertung vornehmen: Das Verfahren mit modularer Multiplikation ist nicht sicher, da man den privaten Schlüssel schnell aus dem öffentlichen Schlüssel bestimmen kann.
Eine zentrale Rolle spielt hierbei der erweiterte euklidische Algorithmus. Dieser Algorithmus ermöglicht es, das modulare Inverse einer Zahl effizient zu berechnen.
