Modulkraft großer Zahlen

8

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?

    
Eng. Aws 27.11.2011, 16:43
quelle

4 Antworten

18

ein Pseudocode

%Vor%

und rufe

an %Vor%     
esskar 27.11.2011, 16:56
quelle
12

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 :

  1. 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

  2. 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.

    
Stephen Canon 27.11.2011 17:00
quelle
5

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.

    
Brett Hale 27.11.2011 16:56
quelle
3

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.

    
user85109 27.11.2011 17:14
quelle