Schnelles Potenzieren in C#

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:

static long PowerLoop(long a, long n, long m)
{
    long result = 1;
    for (long i = 0; i < n; i++)
    {
        result = result * a % m;
    }
    return result;
}

Bei 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.

static long Power(long a, long n, long m)
{
    if (n == 0)
    {
        return 1;
    }
    long half = Power(a, n / 2, m);
    long square = half * half % m;
    if (n % 2 == 1)
    {
        return square * a % m;
    }
    return square;
}

Console.WriteLine(Power(3, 13, 1_000_000_007));
Console.WriteLine(Power(5, 1_000_000_000, 1_000_000_007));

1594323
142848001

Der 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.

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result = result * a % m;
        }
        a = a * a % m;
        n /= 2;
    }
    return result;
}

Console.WriteLine(Power(3, 13, 1_000_000_007));
Console.WriteLine(Power(5, 1_000_000_000, 1_000_000_007));

1594323
142848001

Die 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

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result = result * a % m;
        }
        a = a * a % m;
        n /= 2;
    }
    return result;
}

Console.WriteLine(Power(3, 13, 1_000_000_007));  // 1594323

Schritt 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:

static long multiplications = 0;

static long PowerLoop(long a, long n, long m)
{
    long result = 1;
    for (long i = 0; i < n; i++)
    {
        multiplications++;
        result = result * a % m;
    }
    return result;
}

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            multiplications++;
            result = result * a % m;
        }
        multiplications++;
        a = a * a % m;
        n /= 2;
    }
    return result;
}

long m = 1_000_000_007;
foreach (long n in new long[] { 10, 1_000, 100_000, 10_000_000 })
{
    multiplications = 0;
    PowerLoop(5, n, m);
    long slow = multiplications;
    multiplications = 0;
    Power(5, n, m);
    Console.WriteLine($"n = {n}: Schleife {slow}, schnell {multiplications} Multiplikationen");
}
multiplications = 0;
Power(5, 1_000_000_000, m);
Console.WriteLine($"n = 1000000000: schnell {multiplications} Multiplikationen");

n = 10: Schleife 10, schnell 6 Multiplikationen
n = 1000: Schleife 1000, schnell 16 Multiplikationen
n = 100000: Schleife 100000, schnell 23 Multiplikationen
n = 10000000: Schleife 10000000, schnell 32 Multiplikationen
n = 1000000000: schnell 43 Multiplikationen

Lass 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

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result = result * a % m;
        }
        a = a * a % m;
        n /= 2;
    }
    return result;
}

Die 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?

static long multiplications = 0;

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            multiplications++;
            result = result * a % m;
        }
        multiplications++;
        a = a * a % m;
        n /= 2;
    }
    return result;
}

foreach (long n in new long[] { 15, 16 })
{
    multiplications = 0;
    Power(3, n, 1_000_000_007);
    Console.WriteLine($"{n}: {multiplications} Multiplikationen");
}

Antwort

15: 4 Multiplikationen
16: 5 Multiplikationen

15: 8 Multiplikationen
16: 6 Multiplikationen

15: 15 Multiplikationen
16: 16 Multiplikationen

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:

long m = 10_000_000_019;
Console.WriteLine("long:       " + Power(5, 1_000_000_000, m));
BigInteger exact = BigInteger.ModPow(5, 1_000_000_000, m);
Console.WriteLine("BigInteger: " + exact);

long:       -7139217113
BigInteger: 475867028

long reicht bis 9,2 · 10¹⁸. Bei m = 10.000.000.019 ist das Produkt bis zu 10²⁰, überschreitet die Grenze und läuft ohne Fehler zu einer negativen Zahl über. Sicher ist es, solange m unter etwa 3 · 10⁹ liegt (m² unter 2⁶³); 1.000.000.007 liegt unter der Grenze. Für einen größeren Modul gibt es BigInteger.ModPow (using System.Numerics;), und checked { … } wirft wenigstens OverflowException, statt zu schweigen. Seit .NET 7 gibt es auch Int128 / UInt128.

Die Idee

Das Eingebaute und ein 77-stelliger Exponent

In echtem Code schreibt man eine modulare Potenz nicht von Hand:

BigInteger secret = BigInteger.Pow(2, 255) - 19;
BigInteger p = BigInteger.Pow(2, 127) - 1;
Console.WriteLine("Ziffern im Exponenten: " + secret.ToString().Length);
Console.WriteLine("Multiplikationen beim Quadrieren: " + (secret.GetBitLength() + (long)BigInteger.PopCount(secret)));
Console.WriteLine("5^secret mod p = " + BigInteger.ModPow(5, secret, p));

Ziffern im Exponenten: 77
Multiplikationen beim Quadrieren: 508
5^secret mod p = 97285997395055909576908201857106207893

BigInteger.ModPow quadriert und nimmt den Rest unterwegs. 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.

Probier es aus

Ergänze

Wann geht das aktuelle a ins Ergebnis?

static long Power(long a, long n, long m)
{
    long result = 1;
    a %= m;
    while (n > 0)
    {
        if ()
        {
            result = result * a % m;
        }
        a = a * a % m;
        n /= 2;
    }
    return result;
}

Ü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 BigInteger, ohne Modul, und runde einen halben Cent auf.

Nach 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.

C#: BigInteger.Pow(value, int) ist eine Potenz ohne Modul. Math.Pow ist für double und nicht für ganze Zahlen.

Test

Teste dich

1. Wie viele Multiplikationen braucht das Quadrieren für n = 1.000.000?27: 1.000.000 hat 20 Binärziffern und 7 Einsen1.000.000: eine für jede Einheit von n500.000: die Hälfte, weil n durch 2 geteilt wird

2. Warum nimmt der Code nach jeder Multiplikation den Rest mod m und nicht nur am Ende?Sonst ist das Ergebnis ein anderesSo gibt es weniger MultiplikationenDer Rest am Ende ist derselbe, und so bleiben die Zahlen unter m, und eine Multiplikation kostet so viel wie bei kleinen Zahlen

3. Was ist die eingebaute schnelle modulare Potenz?Math.Pow(a, n) % mBigInteger.ModPow(a, n, m)BigInteger.Pow(a, n) % m

Math.Pow rechnet mit double und verliert schon bei 3⁴⁰ Ziffern. BigInteger.Pow(a, n) % m ist richtig, baut aber zuerst die ganze riesige Zahl. ModPow nimmt den Rest unterwegs.

4. In der rekursiven Version wird die Hälfte mit zwei rekursiven Aufrufen statt mit einem berechnet. Was passiert?Der Stack läuft überDas Ergebnis stimmt, aber die Multiplikationen sind wieder etwa n: Jede Ebene verdoppelt die AufrufeDas Ergebnis ist falsch

5. Wie viele Frames braucht die rekursive Version für n = 1.000.000.000?Einen, weil der Aufruf ein Endaufruf istEtwa 30: einen für jede Halbierung von nEtwa eine Milliarde

Schnelles Potenzieren

Cookies