Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
schnelle modulo-Berechnung
Hi,
es kommt oft vor, dass man a^n = x mod y berechnen muss (z.B. bei Primzahl-Zertifikaten).
Muss man da immer die ganze Prozedur vom Miller-Rabin-Test (schnelle Exponentiation) durchziehen, oder gibt es einen schnelleren, einfacheren Weg?
Wie entscheidet man am schnellsten, ob z.B. 3^78 = 1 mod 79 ist?
Schnellerer Weg: Wie mans nimmt. Für großen n gibt es noch ne Methode mit Laplace Transformation und eine auf Fourier Basis. Sind aber auch nicht wirklich gut per Hand durchzuführen.
=> Die schnelle ist wohl der beste Weg. (solange man nach jeder Multiplikation mit seinem Modul reduziert, sonst wirds groß)
zu deinem Beispiel:
79 ist eine Primzahl. ⇒ Die Restklassen mod 79 bilden einen Körper ⇒
Ordnung der Multiplikativen Gruppe ist 79-1 = 78.
Da die Ordnung eines jeden Elementes die Gruppenordnung teilt (satz von Lagrange) ist also 3^78 = 1.
Also eine schnellere Möglichkeit a^y mod n zu berechnen gibt es nur, wenn du die Ordnung des Elementes a kennst. Dann gilt nämlich a^y mod n = a^(y mod ord(x) ) mod n. Sowas was zum Beispiel in der letzten Klausur dran mit dem 2^69. Da hat man die Ordnung von 2 in den entsprechenden Z ausgerechnet und brauchte dann nur noch wenige Exponentiationen. Das geht allerdings nur wenn n keine Primzahl ist, sonst wirds schwer mit dem Zerlegen.
Der Miller Rabin Test rechnet aber a^(n-1) mod n nur als Abfallprodukt aus. Der Witz beim Miller Rabin ist eigentlich, dass wenn der Fall auftritt, dass man eine Zahl ungleich 1 oder -1 quadriert und dann das Ergebnis von der Zahl^2 = 1 ist, dann ist erkannt, dass die Zahl n keine Primzahl ist. Falls der Miller Rabin ohne Ergebnis durchläuft (also so ein Fall nicht auftrat, dann wird mit dem Ergebnis noch der Fermat test gemacht - sprich a^(n-1) mod n muss 1 sein) Beim Miller Rabin wäre was schnelleres evtl schlecht.