Modulare Exponentiationsrechner

Modulare Exponentiationsrechner

Der Modulare Exponentiationsrechner berechnet \(a^b \bmod n\) — das Erheben einer Basis \(a\) in einen Exponenten \(b\) und das Bestimmen des Restes bei der Division durch einen Modulus \(n\). Er verwendet den binären Exponentiationsalgorithmus (auch bekannt als Square-and-Multiply oder schnelles Potenzieren), der die Anzahl der Operationen von \(O(b)\) Multiplikationen auf nur \(O(\log b)\) reduziert. Dies ist derselbe Algorithmus, der in realen kryptografischen Implementierungen wie RSA, Diffie-Hellman und ElGamal zum Einsatz kommt.

Anwendungen der modularen Exponentiation

Wie der binäre Exponentiationsalgorithmus funktioniert

Die entscheidende Erkenntnis ist, dass wir jeden Exponenten mithilfe seiner Binärdarstellung in eine Summe von Zweierpotenzen zerlegen können. Zum Beispiel ist \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), woraus folgt \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

Der Algorithmus verarbeitet die Binärziffern des Exponenten von links nach rechts:

Pseudocode

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // Bit ist 1
            result = (result × base) mod mod
        exp = exp >> 1        // Rechts-Shift (Division durch 2)
        base = (base × base) mod mod
    return result

Wichtige Formeln

So verwenden Sie den Modularen Exponentiationsrechner

1. Geben Sie die Basis (a) ein: Dies ist die Zahl, die Sie potenzieren möchten. Sie kann positiv oder negativ sein. Geben Sie beispielsweise 7 ein, um 7^256 mod 13 zu berechnen.
2. Geben Sie den Exponenten (b) ein: Dies muss eine nicht-negative Ganzzahl sein. Sie stellt die Potenz dar. Für kryptografische Anwendungen kann diese sehr groß sein (der Rechner unterstützt bis zu 10^18).
3. Geben Sie den Modulus (n) ein: Dies muss eine positive Ganzzahl sein. Es ist die Zahl, durch die Sie teilen, um den Rest zu erhalten. Bei RSA ist dies typischerweise das Produkt zweier großer Primzahlen.
4. Klicken Sie auf Berechnen: Der Rechner berechnet a^b mod n mittels binärer Exponentiation und zeigt das Ergebnis sofort an.
5. Schauen Sie sich die Animation an: Drücken Sie auf Abspielen, um zu sehen, wie der binäre Exponentiationsalgorithmus Schritt für Schritt ausgeführt wird. Jedes Bit des Exponenten wird nacheinander verarbeitet, wobei angezeigt wird, ob der Algorithmus quadriert oder quadriert und multipliziert.
6. Prüfen Sie den Verlauf: Die Schritt-für-Schritt-Tabelle zeigt jede Zwischenrechnung, und der Effizienzvergleich veranschaulicht, wie viel schneller die binäre Exponentiation gegenüber der naiven wiederholten Multiplikation ist.

Warum die binäre Exponentiation schnell ist

Betrachten wir die Berechnung von \(2^{1000} \bmod 13\). Der naive Ansatz würde 999 Multiplikationen erfordern. Die binäre Exponentiation wandelt 1000 in das Binärformat um (1111101000), was 10 Bits entspricht. Sie benötigt höchstens 9 Quadrierungen plus einige Multiplikationen für jedes "1"-Bit — insgesamt etwa 15 Operationen. Das sind etwa 98,5 % weniger Operationen. Bei Exponenten im kryptografischen Maßstab mit Hunderten von Stellen ist der Unterschied astronomisch: Die binäre Methode benötigt Tausende von Operationen, während die naive Methode mehr Operationen erfordern würde, als es Atome im Universum gibt.

FAQ