Montgomery-Potenzierung

4.6 MONTGOMERY-Potenzierung

Bei der Methode nach MONTGOMERY handelt es sich eigentlich um eine Multiplikationsmethode, bei der die Modulo-Reduktion des (Zwischen-) Ergebnisses ohne echte Langzahldivision erfolgen kann [Mon85], [CP05, 9.2.1], [HMV04, 2.2.4]. Da allerdings zuerst eine Transformation beider Faktoren in den MONTGOMERY-“Raum“ vorgenommen werden muß (welche zwei Modulo-Division erfordert) und außerdem einmal der erweiterte GCD-Algorithmus bemüht werden muß, kommen die Geschwindigkeitsvorteile nur bei der Potenzierung wirklich zum tragen.

Um einen leicht verständlichen Zugang zu finden, konzentrieren wir uns auf eine einzelne Multiplikation $c = ab (mod m)$ . Dazu soll eine Zahl $r$ vorausgesetzt werden, die keinen gemeinsamen Teiler mit dem Modul $m$ hat und für die $r > m$ gewährleistet ist. Die MONTGOMERY-Multiplikation kann man nun, unter der Voraussetzung $gcd(r,m)= 1$ (bzw. mit dem Satz von BéZOUT $αr − βm = 1$ ), in folgenden Einzelschritten darstellen:

Berechnung der BéZOUT-Koeffizienten $α,β$ mit Hilfe des erweiterten euklidischen Algorithmus;
Eingangstransformation der Faktoren $a$ und $b$ zu $^a= ar mod m$ und $^b = br mod m$ (eine normale Modulo-Division);
(Wiederholte) Multiplikation im MONTGOMERY-Bereich:
1. Berechnung des Produkts $x= a^⋅^b$ (man beachte, daß hierbei keine Modulo-Reduktion vorgenommen wird);
2. MONTGOMERY-Reduktion von $x= (ar mod m )⋅(br mod m )$ zu $^c= abr mod m = cr mod m$ ;
  Die nötige Korrektur⁶⁹ $−1 ^c= M(x,r,m )= xr mod m$ führt zu einer MONTGOMERY-Darstellung für $c$ (als Voraussetzung für den nächsten Teilschritt).⁷⁰
3. Eine weitere (optionale) Multiplikationen im MONTGOMERY-“Raum“, die $^c$ als einen der Faktoren verwendet;
Rücktransformation des Ergebnisses $^c$ zu $−1 c= c^r mod m$ , ebenfalls eine MONTGOMERY-Reduktion: $c = M (^c,r,m)$ .

MONTGOMERY-Reduktion Zur Herleitung von MONTGOMERY’s effizienter Berechnungsmethode für $M (x,r,m)= xr−1 mod m$ wählen wir als Ausgangspunkt:

Subtraktion beider Gleichungen ergibt

was mit $gcd (r,m) = αr− β m = 1$ zu

m (βx mod r)+ x= (v− u)rm + r(αx mod m)

führt.⁷¹

Mit dem Wissen, daß es sich bei $α$ um das multiplikativ inverse Element von $r$ im Restklassensystem modulo $m$ handelt ( $− 1 α = r (mod m)$ , $−1 β = − m (mod r)$ ), stellen wir noch um:

m(β-x mod-r)−-(v−-u)rm-+-x αx mod m = r

und gewinnen letztlich MONTGOMERY’s Reduktionsformel.

M (x,r,m)= xr−1 mod m = m-(βx-mod-r)+-x− (v− u)m r

(4.40)

Praktisch benötigt man $u$ und $v$ nicht, sondern geht meist nach folgendem Algorithmus vor:

Algorithmus 11: MONTGOMERY-Reduktion

Ensure: $−1 y = xr mod m$ $t ⇐ βx mod r$
$mt+ x y ⇐ ------ r$
if $y≥ m$ then
$y ⇐ y − m$
end if

Bei geschickter Wahl von $r$ zum Beispiel als $r = 2s$ sind für alle (Modulo-) Divisionen in Formel 4.40 nur logische oder Schiebeoperationen nötig.⁷² Um $gcd(2s,m)= 1$ zu garantieren ist die einfachste Bedingung die, $m$ als ungerade vorauszusetzen.⁷³