Modulare Exponentiationsrechner

Berechnen Sie die modulare Exponentiation a^b mod n effizient mit dem Algorithmus der binären Exponentiation (schnelles Potenzieren). Geben Sie Basis, Exponent und Modulus ein, um sofortige Ergebnisse mit einer schrittweisen Aufschlüsselung der Square-and-Multiply-Methode, einer Visualisierung der binären Zerlegung und dem kryptografischen Kontext zu erhalten.

Embed Modulare Exponentiationsrechner Widget

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

🔐

RSA-Verschlüsselung

Verschlüsseln und Entschlüsseln von Nachrichten mit modularen Exponenten großer Primzahlprodukte

🤝

Diffie-Hellman

Schlüsselaustauschprotokoll zur Berechnung von g^a mod p für sichere gemeinsame Geheimnisse

✍

Digitale Signaturen

DSA, ECDSA und EdDSA basieren alle auf modularer Exponentiation

🧪

Primzahltests

Fermat- und Miller-Rabin-Tests nutzen a^(n-1) mod n zur Überprüfung der Primalität

🏆

Competitive Programming

Modulare Arithmetik mit schnellem Potenzieren ist essentiell für Wettbewerbsaufgaben

🔗

Blockchain

Proof-of-Work und kryptografisches Hashing stützen sich auf modulare Arithmetik

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:

Schritt 1: Wandeln Sie den Exponenten \(b\) in das Binärsystem um.

Schritt 2: Initialisieren Sie das Ergebnis = 1 (oder = Basis, falls das erste Bit 1 ist).

Schritt 3: Für jedes folgende Bit: Quadrieren Sie das Ergebnis (mod n). Wenn das Bit 1 ist, multiplizieren Sie zusätzlich mit der Basis (mod n).

Schritt 4: Nachdem alle Bits verarbeitet wurden, ist das Ergebnis \(a^b \bmod n\).

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

Eigenschaft	Formel	Beschreibung
Modulare Exponentiation	\(a^b \bmod n\)	Rest von a^b geteilt durch n
Kleiner Fermatscher Satz	\(a^{p-1} \equiv 1 \pmod{p}\)	Für Primzahl p und ggT(a,p)=1
Satz von Euler	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Für ggT(a,n)=1, wobei φ die Eulersche Phi-Funktion ist
Komplexität (Binär)	\(O(\log b)\) Multiplikationen	Höchstens 2·log₂(b) modulare Multiplikationen
RSA-Verschlüsselung	\(c = m^e \bmod n\)	Nachricht m mit öffentlichem Schlüssel (e, n) verschlüsseln
RSA-Entschlüsselung	\(m = c^d \bmod n\)	Geheimtext c mit privatem Schlüssel d entschlüsseln

So verwenden Sie den Modularen Exponentiationsrechner

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.
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).
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.
Klicken Sie auf Berechnen: Der Rechner berechnet a^b mod n mittels binärer Exponentiation und zeigt das Ergebnis sofort an.
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.
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

Was ist modulare Exponentiation?

Die modulare Exponentiation berechnet (a^b) mod n — sie erhebt eine Basis in einen Exponenten und nimmt dann den Rest bei der Division durch einen Modulus. Es ist die Kernoperation in der Public-Key-Kryptografie (RSA, Diffie-Hellman, ElGamal) und wird ausgiebig in der Zahlentheorie, beim Competitive Programming und in der Informatik verwendet. Die binäre Exponentiationsmethode berechnet dies effizient in O(log b) Multiplikationen.

Wie funktioniert die binäre Exponentiation (Square-and-Multiply)?

Die binäre Exponentiation wandelt den Exponenten in seine binäre Darstellung um und verarbeitet dann jedes Bit von links nach rechts (oder von rechts nach links). Für jedes Bit wird das aktuelle Ergebnis modulo n quadriert. Wenn das Bit 1 ist, wird das Ergebnis zusätzlich mit der Basis modulo n multipliziert. Dies reduziert die Anzahl der Multiplikationen von b−1 (naive Methode) auf höchstens 2×log₂(b), wodurch Berechnungen mit riesigen Exponenten erst möglich werden.

Warum ist die modulare Exponentiation in der Kryptografie wichtig?

Die RSA-Verschlüsselung berechnet c = m^e mod n für die Verschlüsselung und m = c^d mod n für die Entschlüsselung, wobei n ein Produkt aus zwei großen Primzahlen ist und die Exponenten hunderte Stellen lang sein können. Ohne schnelle modulare Exponentiation wären diese Operationen computertechnisch unmöglich. Die Sicherheit beruht darauf, dass die Umkehroperation (Berechnung des diskreten Logarithmus) als rechentechnisch nicht durchführbar gilt.

Kann die Basis negativ sein?

Ja, negative Basen werden vollständig unterstützt. Der Rechner reduziert die Basis zuerst modulo n (unter Verwendung der Modulo-Arithmetik von Python, die für positive n immer ein nicht-negatives Ergebnis liefert). Zum Beispiel: (−3)^2 mod 7 = 9 mod 7 = 2. Negative Ergebnisse treten nie auf, da die modulare Reduktion immer einen Wert im Bereich [0, n−1] erzeugt.

Was passiert, wenn der Modulus 1 ist?

Jede ganze Zahl modulo 1 ist gleich 0. Dies liegt daran, dass das Teilen einer beliebigen ganzen Zahl durch 1 die Zahl selbst mit einem Rest von 0 ergibt. Somit ist a^b mod 1 = 0 für alle Werte von a und b. Der Rechner behandelt dies als Sonderfall.

Zitieren Sie diesen Inhalt, diese Seite oder dieses Tool als:

"Modulare Exponentiationsrechner" unter https://MiniWebtool.com/de/modulare-exponentiationsrechner/ von MiniWebtool, https://MiniWebtool.com/

vom MiniWebtool-Team. Aktualisiert: 2026-04-16

Sie können auch unseren KI-Mathematik-Löser GPT ausprobieren, um Ihre mathematischen Probleme durch natürliche Sprachfragen und -antworten zu lösen.

Andere verwandte Tools:

Chinesischer Restsatz Rechner

Euler Totient Funktion Rechner

exponenten-rechner-hohe-präzision

Modularer Multiplikativer Inverser Rechner

Primfaktorzerlegung Rechner

Primitivwurzel-Rechner

Modulare Exponentiationsrechner

Modulare Exponentiationsrechner

Anwendungen der modularen Exponentiation

Wie der binäre Exponentiationsalgorithmus funktioniert

Pseudocode

Wichtige Formeln

So verwenden Sie den Modularen Exponentiationsrechner

Warum die binäre Exponentiation schnell ist

FAQ

Andere verwandte Tools:

Erweiterte Rechenoperationen:

Ausgewählte Werkzeuge: