Schnelles Potenzieren
Kurz gesagt: Schnelles Potenzieren berechnet aⁿ mit O(log n) Multiplikationen, indem es quadriert und die Binärziffern von n liest; nimmt man nach jedem Schritt den Rest, ergibt das die modulare Potenz.
Problem
Der Schlüssel einer HTTPS-Verbindung
Wenn der Browser eine HTTPS-Seite öffnet, einigen er und der Server sich auf einen gemeinsamen geheimen Schlüssel, ohne ihn über das Netz zu schicken. In der klassischen Version (Diffie–Hellman) berechnet jede Seite eine modulare Potenz: gᵃ mod p, wobei a eine geheime Zahl mit Dutzenden Stellen ist. Dieselbe Berechnung steckt in RSA-Signaturen und im Hash eines Textes, der mit Potenzen einer Basis multipliziert.
Der naive Weg ist eine Schleife, die n-mal multipliziert:
def power_loop(a, n, m): result = 1 for _ in range(n): result = result * a % m return resultBei einem 77-stelligen Exponenten (zum Beispiel 2²⁵⁵ − 19) sind das etwa 6 · 10⁷⁶ Multiplikationen. Bei einer Milliarde Multiplikationen pro Sekunde würde die Schleife 10⁶⁷ Sekunden laufen, und das Universum ist etwa 4 · 10¹⁷ Sekunden alt. Trotzdem schafft der Server Tausende solcher Verbindungen pro Sekunde.
Die Idee
Das Quadrat der Hälfte
3¹³ braucht keine 13 Multiplikationen. 3¹³ = 3⁶ · 3⁶ · 3, und 3⁶ = 3³ · 3³. Jeder Schritt halbiert den Exponenten:
- aⁿ = (aⁿᐟ²)², wenn n gerade ist;
- aⁿ = (aⁿᐟ²)² · a, wenn n ungerade ist (n / 2 ist Ganzzahldivision);
- a⁰ = 1: Das ist der Basisfall.
def power(a, n, m): if n == 0: return 1 half = power(a, n // 2, m) square = half * half % m if n % 2 == 1: return square * a % m return square
print(power(3, 13, 1_000_000_007))print(power(5, 1_000_000_000, 1_000_000_007))1594323142848001Der Rest mod m nach jeder Multiplikation hält die Zahlen klein: (x · y) mod m ist dasselbe wie ((x mod m) · (y mod m)) mod m. Hier ist m = 1.000.000.007, eine Primzahl und eine verbreitete Grenze bei Hashes und in Programmierwettbewerben.
Was kostet das? Jeder Aufruf teilt n durch 2, genau wie die binäre Suche, also ist die Tiefe etwa log₂ n: Für n = 10⁹ sind das 30 Frames. Der Aufruf ist kein Endaufruf (das Quadrieren kommt danach), aber aus der ersten Lektion weißt du, dass 30 Frames für den Stack nichts sind. Die Arbeit sind höchstens zwei Multiplikationen pro Ebene: O(log n) statt O(n).
Die Idee
Ohne Rekursion: die Binärziffern von n
Eine Schleife kann dasselbe. 13 ist binär 1101: 13 = 8 + 4 + 1, also 3¹³ = 3⁸ · 3⁴ · 3¹. Die Schleife liest die Ziffern von n von rechts nach links (n % 2 ist die letzte, und n /= 2 entfernt sie) und hält ein quadriertes a: 3¹, 3², 3⁴, 3⁸ … Bei einer Ziffer 1 geht das aktuelle a ins Ergebnis.
def power(a, n, m): result = 1 a %= m while n > 0: if n % 2 == 1: result = result * a % m a = a * a % m n //= 2 return result
print(power(3, 13, 1_000_000_007))print(power(5, 1_000_000_000, 1_000_000_007))1594323142848001Die Multiplikationen sind so viele wie die Ziffern von n (ein Quadrieren pro Ziffer) plus die Einsen darin (je eine Multiplikation des Ergebnisses). Das ist die Version, die Bibliotheken benutzen: keine Rekursion und keine Abhängigkeit von der Stackgröße.
Sieh es dir an
Die Quadrate gehen ins Ergebnis
def power(a, n, m): result = 1 a %= m while n > 0: if n % 2 == 1: result = result * a % m a = a * a % m n //= 2 return result
print(power(3, 13, 1_000_000_007)) # 1594323Schritt für Schritt, in Worten
- result beginnt bei 1. n = 13, binär 1101: Jede Binärziffer entscheidet, ob a ins Ergebnis geht.
- n = 13 ist ungerade: result = 1 · 3 = 3. Dann wird a zu 3² = 9 und n zu 6.
- n = 6 ist gerade: result bleibt 3. Nur a wird quadriert: 9 · 9 = 81 = 3⁴, und n = 3.
- n = 3: result = 3 · 81 = 243 = 3⁵. a = 6561 = 3⁸, n = 1.
- n = 1: result = 243 · 6561 = 1594323 = 3¹³, denn 13 = 8 + 4 + 1. Die Schleife quadriert a noch einmal: 3¹⁶ ist eine Multiplikation, die niemand braucht.
- n = 0, und die Schleife hört auf: 7 Multiplikationen statt 13. Bei n = 10⁹ sind es 43 statt einer Milliarde.
Sieh es dir an
Die Multiplikationen zählen
Beide Versionen mit einem Zähler, für Exponenten von 10 bis 10.000.000, und die schnelle auch für eine Milliarde:
multiplications = 0
def power_loop(a, n, m): global multiplications result = 1 for _ in range(n): multiplications += 1 result = result * a % m return result
def power(a, n, m): global multiplications result = 1 a %= m while n > 0: if n % 2 == 1: multiplications += 1 result = result * a % m multiplications += 1 a = a * a % m n //= 2 return result
m = 1_000_000_007for n in [10, 1_000, 100_000, 10_000_000]: multiplications = 0 power_loop(5, n, m) slow = multiplications multiplications = 0 power(5, n, m) print(f"n = {n}: Schleife {slow}, schnell {multiplications} Multiplikationen")multiplications = 0power(5, 1_000_000_000, m)print(f"n = 1000000000: schnell {multiplications} Multiplikationen")n = 10: Schleife 10, schnell 6 Multiplikationenn = 1000: Schleife 1000, schnell 16 Multiplikationenn = 100000: Schleife 100000, schnell 23 Multiplikationenn = 10000000: Schleife 10000000, schnell 32 Multiplikationenn = 1000000000: schnell 43 MultiplikationenLass sie auch hier laufen. Bench zählt nach derselben Regel (eine Multiplikation mod m ist eine Operation), also sind die Zahlen die in der Ausgabe oben. Eine Milliarde lassen wir mit der naiven Schleife nicht laufen: Bench schätzt sie aus der Kurve.
- Schleife: n Multiplikationen
O(n) - Quadrieren
O(log n)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 | n = 10.000.000 | n = 1.000.000.000 |
|---|---|---|---|---|---|
| Schleife: n Multiplikationen | 10 | 1.000 | 100.000 | 10.000.000 | ≈ 1.000.000.000 |
| Quadrieren | 6 | 16 | 23 | 32 | 43 |
def power(a, n, m): result = 1 a %= m while n > 0: if n % 2 == 1: result = result * a % m a = a * a % m n //= 2 return resultDie naive Schleife wächst wie n, die schnelle wie die Zahl der Ziffern von n: Ein zehnmal größeres n fügt etwa 3,3 Binärziffern hinzu, also 3 bis 7 Multiplikationen.
Probier es aus
15 oder 16
Welcher Exponent braucht mehr Multiplikationen?
multiplications = 0
def power(a, n, m): global multiplications result = 1 a %= m while n > 0: if n % 2 == 1: multiplications += 1 result = result * a % m multiplications += 1 a = a * a % m n //= 2 return result
for n in [15, 16]: multiplications = 0 power(3, n, 1_000_000_007) print(f"{n}: {multiplications} Multiplikationen")15 = 1111: vier Ziffern und vier Einsen, 8 Multiplikationen. 16 = 10000: fünf Ziffern und eine Eins, 6 Multiplikationen. Ein größerer Exponent heißt nicht mehr Arbeit: Es zählen die Ziffern und die Einsen.
Die Idee
Wenn das Produkt nicht hineinpasst
Der Rest hält die Zahlen unter m, aber das Produkt zweier solcher Zahlen ist bis zu m². Passt m² nicht in den Typ, ist die Berechnung falsch, und das stillschweigend. Hier dieselbe Potenz mit einem größeren Modul:
m = 10_000_000_019print("power:", power(5, 1_000_000_000, m))print("pow: ", pow(5, 1_000_000_000, m))power: 475867028pow: 475867028int nach Bedarf, also gibt derselbe Code auch bei einem großen Modul die richtige Antwort. Der Preis ist, dass jede Multiplikation großer Zahlen langsamer ist. Das eingebaute pow(a, n, m) macht dasselbe Quadrieren, aber in C.Die Idee
Das Eingebaute und ein 77-stelliger Exponent
In echtem Code schreibt man eine modulare Potenz nicht von Hand:
secret = 2**255 - 19p = 2**127 - 1print("Ziffern im Exponenten: " + str(len(str(secret))))print("Multiplikationen beim Quadrieren: " + str(secret.bit_length() + secret.bit_count()))print("5^secret mod p =", pow(5, secret, p))Ziffern im Exponenten: 77Multiplikationen beim Quadrieren: 5085^secret mod p = 97285997395055909576908201857106207893pow(a, n, m) mit drei Argumenten quadriert und nimmt den Rest unterwegs. a ** n % m ist richtig, baut aber zuerst das ganze aⁿ: Bei einem 77-stelligen Exponenten würde es nie fertig. 508 Multiplikationen von 39-stelligen Zahlen statt 6 · 10⁷⁶: Deshalb wird der Schlüssel in Millisekunden vereinbart. Bibliotheken brauchen noch weniger, weil sie mehrere Ziffern auf einmal ansehen, aber die Idee ist dieselbe.
Probier es aus
Finde den Fehler
Diese Version liefert das richtige Ergebnis. Aber für n = 1.000.000 macht sie 2.048.575 Multiplikationen statt 27. Welche Zeile ist schuld?
Wähle die Zeile mit dem Fehler.
Die Hälfte wird zweimal berechnet. Jede Ebene verdoppelt die Aufrufe: 2, 4, 8 … und ganz unten sind es etwa n. Die Tiefe ist weiterhin log₂ n, also merkt der Stack nichts, aber die Arbeit ist wieder O(n). Die Korrektur: die Hälfte in eine Variable legen und dann half * half.
Probier es aus
Ergänze
Wann geht das aktuelle a ins Ergebnis?
def power(a, n, m):
result = 1
a %= m
while n > 0:
if :
result = result * a % m
a = a * a % m
n //= 2
return resultWenn die letzte Binärziffer von n eine 1 ist, das heißt, wenn n ungerade ist.
Übung
Zinsen auf den Cent
Löse die Aufgabe in deinem Editor.
Worauf die Einlage wächst. Du legst 1000 € zu 1 % Zinsen pro Monat an, die auf den Betrag addiert werden. Lies die Zahl der Monate und gib den auf den Cent gerundeten Betrag aus. Rechne genau, mit ganzen Zahlen: 1000 € sind 100.000 Cent, und nach n Monaten ist der Betrag 100.000 · 101ⁿ / 100ⁿ Cent. Schreibe dein eigenes schnelles Potenzieren mit int, ohne Modul, und runde einen halben Cent auf.
120Nach 120 Monaten: 3300,39 €Bei 120 Monaten sind die Multiplikationen auch mit der naiven Schleife wenige. Hier aber wachsen die Zahlen (101¹²⁰ hat 241 Ziffern), also kostet jede weitere Multiplikation mehr, und gesparte Multiplikationen zählen noch mehr.
Weitere Aufgaben
- Tageszinsen für 30 Jahre. Dasselbe mit 0,01 % pro Tag für 10.950 Tage. Zähle die Multiplikationen beider Versionen.
- Die letzten Ziffern. Gib die letzten 6 Ziffern von 2¹⁰⁰⁰⁰⁰⁰⁰⁰⁰ aus (Modul 1.000.000), ohne die ganze Zahl zu bauen.
Genauer
Mehr über Potenzen
Genauer, für Neugierige
Fibonacci-Zahlen in O(log n). Dasselbe Quadrieren funktioniert mit einer 2 × 2-Matrix statt einer Zahl: Die n-te Fibonacci-Zahl ergibt sich aus der n-ten Potenz von [[1, 1], [1, 0]], mit etwa 2 log₂ n Matrixmultiplikationen.
Elliptische Kurven. Heute einigt sich TLS meist mit einer elliptischen Kurve (X25519) auf den Schlüssel. Dort gibt es statt der Multiplikation das „Addieren von Punkten“ und statt des Quadrierens das „Verdoppeln“, aber der Algorithmus ist derselbe: Double-and-Add über die Binärziffern der geheimen Zahl.
Konstante Zeit. Die Schleife in der Lektion multipliziert das Ergebnis nur bei einer Ziffer 1. Wer die Zeit misst, kann erraten, wie viele Einsen die geheime Zahl hat. Deshalb machen kryptografische Bibliotheken für jede Ziffer dieselbe Arbeit (die Montgomery-Leiter), und deshalb schreibt man Kryptografie nicht von Hand, sondern nimmt sie aus einer Bibliothek.
- Python:
pow(a, -1, m)(seit 3.8) liefert das Inverse von a mod m.a ** nmit ganzen Zahlen ist exakt, wächst aber unbegrenzt.
Test