Ich versuche den SAFER + Algorithmus zu implementieren. Der Algorithmus erfordert das Auffinden des Moduls einer Potenzfunktion wie folgt:
%Vor%Die Variable x ist ein Byte und kann daher von 0 bis 255 reichen. Entsprechend kann das Ergebnis der Potenzfunktion SEHR groß sein, was zu falschen Werten führt, wenn es mit 32- oder 64-Bit-Ganzzahlen implementiert wird.
Wie kann ich diese Berechnung durchführen?
Führen Sie die Potenzierung durch wiederholtes Quadrieren durch, und reduzieren Sie sie nach jeder Operation um den Modul. Dies ist eine sehr Standardtechnik.
Ein funktionierendes Beispiel: 45^13 mod 257 :
Berechne zuerst 45 ^ 2, 45 ^ 4, 45 ^ 8 mod 257:
45 ^ 2 mod 257 = 2025 mod 257 = 226
45 ^ 4 mod 257 = 226 ^ 2 mod 257 = 51076 mod 257 = 190
45 ^ 8 mod 257 = 190 ^ 2 mod 257 = 36100 mod 257 = 120
Verwenden Sie dann die binäre Erweiterung von 13, um diese zu kombinieren, um das Ergebnis zu erhalten:
45 ^ 13 mod 257 = 45 ^ 1 * 45 ^ 4 * 45 ^ 8 mod 257
45 ^ 13 mod 257 = 45 * 190 * 120 mod 257
45 ^ 13 mod 257 = 8550 * 120 mod 257
45 ^ 13 mod 257 = 69 * 120 mod 257
45 ^ 13 mod 257 = 8280 mod 257
45 ^ 13 mod 257 = 56
Beachten Sie, dass die Zwischenergebnisse der Berechnung nie größer als 257 * 257 sind. Dies kann einfach in einem 32-Bit-Integer-Typ durchgeführt werden.
Der grundlegende Ansatz besteht darin, abhängig vom Exponentenbit zu quadrieren oder zu multiplizieren und die modulare Reduktion in jedem Schritt durchzuführen. Der Algorithmus wird (binäre) modulare Exponentiation genannt.
Betrachten Sie die einfache Identität:
%Vor%Beachten Sie auch, dass
%Vor%Andere Potenzen werden trivial berechnet, wenn Sie die binäre Darstellung des letzten Exponenten kennen, den Sie berechnen möchten.
Tags und Links algorithm language-agnostic math modulus