Schnelle modulare Exponentiation

Wie beim m-ary-Verfahren werden auch beim ’Sliding-Window’ zun¨chst die anibi berechnet a und in einer Tabelle gespeichert. Die Anzahl der Multiplikationen f¨r die Berechnung der u nibi a reduziert sich allerdings erheblich. Da die nibi immer ein f¨hrendes Eins-Bit haben, u kann n¨mlich auf die untere H¨lfte der Tabelle verzichtet werden. Um die Tabelle aufzubaua a en, muss a zun¨chst d − 1 mal modular quadriert werden. Dadurch erh¨lt man den ersten a a Tabelleneintrag. Alle weiteren Tabelleneintr¨ge erh¨lt man durch wiederholtes Multiplizieren a a mit a. Vollst¨ndig ist die Tabelle dann nach weiteren 2d−1 − 1 Multiplikationen. Insgesamt a sind f¨r die Berechnung der anibi also d − 1 + 2d−1 − 1 = d − 2 + 2d−1 modulare Multipliu ∗ kationen notwendig. Der Restfaktor anib findet sich eventuell nicht in der Tabelle, da nib∗ k¨rzer als d sein kann. Er muss separat berechnet werden. Erfolgt dies mittels Square and u Multiply, so kann die Berechnung mit der Berechnung der anibi verschr¨nkt werden. Zu den a sowieso ausgef¨hrten Quadrierungen kommen dann nach Abschnitt 5.1 noch durchschnittu [...]

Die Fenstertechnik [3], auch Sliding Window Techniques genannt, basiert auf der m-aryMethode. Auch hier wird der Exponent in gleich große Bl¨cke zerlegt. Allerdings werden o nur Bl¨cke mit f¨hrenden Eins-Bits ausgew¨hlt. Dazu wird ein d-breites ’Fenster’ auf den o u a Exponenten gelegt. Der Fensterinhalt wird dann als Nibble nibi gew¨hlt, wenn das h¨chsta o wertige Bit gleich Eins ist. Anschließend wird das Fenster um d Stellen weiter nach rechts verschoben. Ist das h¨chstwertige Bit wieder Eins, wird erneut ein Nibble gew¨hlt. Wenn o a nicht, wird das Fenster wiederholt um jeweils eine Stelle weiter nach rechts verschoben bis es Eins ist. Betrachtet man Gleichung 5.5, so sieht man, dass f¨hrende Nullbits ubersprungen u ¨ nibi werden k¨nnen, da sie f¨r die Berechnung der a o u keinen Enfluss haben. Allerdings muss f¨r jedes ubersprungene Bit vor der Multiplikation mit anibi einmal quadriert werden. Sei si u ¨ die Anzahl der vor dem Nibble nibi ubersprungenen Bits und z die Anzahl der verbleiben¨ den, niederwertigen Exponentenbits plus der zuvor ubersprungenen Null-Bits, dann wird aus ¨ [...]

Mit Einbeziehung eines verk¨rzten Restnibbles w¨re die Anzahl der Multiplikationen noch u a etwas geringer. Denn die Anzahl der Werte, die das Restnibble annehmen kann, ist geringer als die der anderen Nibbles, und somit die Wahrscheinlichkeit, dass es gleich Null ist, etwas h¨her. Auf diese Betrachtung wird im Folgenden aber verzichtet und mit 5.6 weitergearbeitet. o F¨r einige gr¨ßere Exponenten ist die Gleichung 5.6 ausgewertet worden. Das Ergebnis findet u o sich in Tabelle 5.9 und Abbildung 5.1. Dort kann die optimale Nibblebreite leicht abgelesen werden. Will man die optimalen Nibblebreiten f¨r beliebig lange Exponenten ermitteln, so u lassen sich diese uber die Nullstellenberechnung der ersten Ableitung von 5.6 ermitteln. ¨ Das m-ary-Verfahren mit richtig gew¨hlter Nibblebreite stellt eine erhebliche Verbesserung a gegen¨ber Square-and-Multiply b.z.w. der Bin¨rmethode dar. In Tabelle 5.10 wird die Veru a ringerung der ben¨tigten Multiplikationen prozentual dargestellt. o In Listing 5.2 erkennt man, dass f¨r jeden Wert, den ein Nibble annehmen kann, ein Register u zur Verf¨gung gestellt werden muss. Bei einer Nibblebreite von d sind dies 2d Register. u Abweichend von Listing 5.2 kann das Ergebnis statt in der Variablen erg in Register Null gespeichert werden. Es sind somit insgesamt 2d Register notwendig. [...]