Schnelles modulares Potenzieren

Schnelles modulares Potenzieren

Studium
a2k≡(ak)2,a2k+1≡(ak)2⋅a(modm)a^{2k} \equiv \left(a^{k}\right)^2, \qquad a^{2k+1} \equiv \left(a^{k}\right)^2 \cdot a \pmod m

Voraussetzung: a∈Z,a \in \mathbb{Z}, k∈N0,k \in \mathbb{N}_0, m∈N,m \in \mathbb{N}, m≥2m \geq 2

aa
Basis, eine ganze Zahl
kk
halber Exponent, natürliche Zahl oder 0
mm
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 an mod ma^{n} \bmod m mit sehr großem nn kommen in der Kryptographie ständig vor. n−1n - 1 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 aa.
  • Nach jedem Schritt reduziert man modulo mm. Das ist nach den Rechenregeln für Kongruenzen erlaubt, und alle Zwischenergebnisse bleiben kleiner als m2m^2.

Praktisch liest man dafür die Binärdarstellung des Exponenten. Zwei gleichwertige Varianten:

  • Von rechts: die Potenzen a1,a2,a4,a8,…a^1, a^2, a^4, a^8, \ldots durch fortgesetztes Quadrieren bestimmen und die multiplizieren, deren Bit 11 ist.
  • Von links: mit 11 starten und die Bits vom höchsten zum niedrigsten durchgehen; bei jedem Bit quadrieren, bei einer 11 zusätzlich mit aa multiplizieren.

Hat nn in Binärdarstellung LL Stellen, braucht man höchstens L−1L - 1 Quadrierungen und L−1L - 1 zusätzliche Multiplikationen, also höchstens etwa 2log⁡2n2\log_2 n statt n−1n - 1. Für einen 2048-Bit-Exponenten sind das rund 4000 statt 220482^{2048} Schritte.

Beispiele

313 mod 173^{13} \bmod 17 von rechts: 13=8+4+1=1101213 = 8 + 4 + 1 = 1101_2. Fortgesetztes Quadrieren modulo 1717:

Potenz313^1323^2343^4383^8
Rest mod 17391316

Dabei ist 92=81≡139^2 = 81 \equiv 13 und 132=169≡1613^2 = 169 \equiv 16. Multipliziert werden die Potenzen zu den Einsen im Exponenten:

313=38⋅34⋅31≡16⋅13⋅3=624≡12(mod17)3^{13} = 3^8 \cdot 3^4 \cdot 3^1 \equiv 16 \cdot 13 \cdot 3 = 624 \equiv 12 \pmod{17}

Dasselbe von links: Die Bits sind 1,1,0,11, 1, 0, 1. Start mit 11:

  • Bit 11: 12⋅3=31^2 \cdot 3 = 3
  • Bit 11: 32⋅3=27≡103^2 \cdot 3 = 27 \equiv 10
  • Bit 00: 102=100≡1510^2 = 100 \equiv 15
  • Bit 11: 152⋅3=675≡1215^2 \cdot 3 = 675 \equiv 12

750 mod 137^{50} \bmod 13: 50=32+16+2=110010250 = 32 + 16 + 2 = 110010_2. Quadrieren liefert 72≡107^2 \equiv 10, 74≡97^4 \equiv 9, 78≡37^8 \equiv 3, 716≡97^{16} \equiv 9, 732≡37^{32} \equiv 3. Also

750=732⋅716⋅72≡3⋅9⋅10=270≡10(mod13)7^{50} = 7^{32} \cdot 7^{16} \cdot 7^{2} \equiv 3 \cdot 9 \cdot 10 = 270 \equiv 10 \pmod{13}

Das sind 55 Quadrierungen und 22 Multiplikationen statt 4949 Multiplikationen. Kontrolle mit dem kleinen Satz von Fermat: 712≡17^{12} \equiv 1 und 50 mod 12=250 \bmod 12 = 2, also 750≡72≡107^{50} \equiv 7^2 \equiv 10.

Typische Fehler

  • Erst am Ende reduzieren. Wer 3133^{13} voll ausrechnet und dann teilt, verliert den Vorteil; bei großen Zahlen läuft der Speicher über. Nach jedem Schritt modulo mm rechnen.
  • Den Exponenten modulo mm reduzieren. Es ist 750≡107^{50} \equiv 10, aber 750 mod 13=711≡2(mod13)7^{50 \bmod 13} = 7^{11} \equiv 2 \pmod{13}. Bei ggT⁡(a,m)=1\operatorname{ggT}(a, m) = 1 darf man den Exponenten modulo φ(m)\varphi(m) reduzieren (Satz von Euler), hier modulo 1212.
  • Die Bitreihenfolge verwechseln. Beim Verfahren von links beginnt man mit dem höchsten Bit; von rechts gehört das niedrigste Bit zu a1a^1.

Verwandte Formeln