Schnelles modulares Potenzieren
Voraussetzung:
- Basis, eine ganze Zahl
- halber Exponent, natürliche Zahl oder 0
- Modul, natürliche Zahl ab 2
Große Potenzen modulo m berechnet man durch wiederholtes Quadrieren und Multiplizieren, gesteuert von der Binärdarstellung des Exponenten.
Erklärung
Potenzen wie mit sehr großem kommen in der Kryptographie ständig vor. Multiplikationen wären viel zu viele, und die Zwischenergebnisse würden riesig. Das Square-and-Multiply-Verfahren löst beide Probleme:
- Man halbiert den Exponenten immer wieder: Ein gerader Exponent wird durch Quadrieren erreicht, ein ungerader durch Quadrieren und eine zusätzliche Multiplikation mit .
- Nach jedem Schritt reduziert man modulo . Das ist nach den Rechenregeln für Kongruenzen erlaubt, und alle Zwischenergebnisse bleiben kleiner als .
Praktisch liest man dafür die Binärdarstellung des Exponenten. Zwei gleichwertige Varianten:
- Von rechts: die Potenzen durch fortgesetztes Quadrieren bestimmen und die multiplizieren, deren Bit ist.
- Von links: mit starten und die Bits vom höchsten zum niedrigsten durchgehen; bei jedem Bit quadrieren, bei einer zusätzlich mit multiplizieren.
Hat in Binärdarstellung Stellen, braucht man höchstens Quadrierungen und zusätzliche Multiplikationen, also höchstens etwa statt . Für einen 2048-Bit-Exponenten sind das rund 4000 statt Schritte.
Beispiele
von rechts: . Fortgesetztes Quadrieren modulo :
| Potenz | ||||
|---|---|---|---|---|
| Rest mod 17 | 3 | 9 | 13 | 16 |
Dabei ist und . Multipliziert werden die Potenzen zu den Einsen im Exponenten:
Dasselbe von links: Die Bits sind . Start mit :
- Bit :
- Bit :
- Bit :
- Bit :
: . Quadrieren liefert , , , , . Also
Das sind Quadrierungen und Multiplikationen statt Multiplikationen. Kontrolle mit dem kleinen Satz von Fermat: und , also .
Typische Fehler
- Erst am Ende reduzieren. Wer voll ausrechnet und dann teilt, verliert den Vorteil; bei großen Zahlen läuft der Speicher über. Nach jedem Schritt modulo rechnen.
- Den Exponenten modulo reduzieren. Es ist , aber . Bei darf man den Exponenten modulo reduzieren (Satz von Euler), hier modulo .
- Die Bitreihenfolge verwechseln. Beim Verfahren von links beginnt man mit dem höchsten Bit; von rechts gehört das niedrigste Bit zu .