Rechner für modulare Exponentiation

Q: Wie berechne ich eine Potenz modulo m von Hand?

Mit der Methode „Quadrieren und Multiplizieren“. Reduzieren Sie zuerst die Basis: Ersetzen Sie b durch b bmod m. Schreiben Sie dann den Exponenten binär und quadrieren Sie die Basis wiederholt, wobei Sie nach jedem Schritt modulo m reduzieren: b^2, b^4, b^8, b^16, ldots. Multiplizieren Sie schließlich nur die Quadrate, die zu den 1-Bits des Exponenten gehören, und reduzieren Sie dabei jedes Mal modulo m. So bleibt jeder Zwischenwert unter m^2.

Q: Warum liegt das Ergebnis von b^e mod m immer zwischen 0 und m-1?

Weil die modulare Arithmetik mit kleinsten nicht-negativen Resten arbeitet. Der Ausdruck b^e bmod m ist definiert als der Rest bei der Division von b^e durch m, und Divisionsreste erfüllen stets 0 ≤ c ≤ m-1. Auch eine negative Basis wird zunächst in den zugehörigen positiven Rest umgewandelt, das Ergebnis ist also nie negativ.

Q: Wie finde ich die letzte Ziffer einer großen Potenz (z. B. 7^100)?

Das ist eine modulare Exponentiation im Gewande: Die letzte Ziffer einer Zahl ist diese Zahl modulo 10. Berechnen Sie also hier 7^100 bmod 10. Ebenso sind die letzten beiden Ziffern der Wert modulo 100 und die letzten drei Ziffern der Wert modulo 1000. Ein klassischer Kniff bei Wettbewerbs- und Hausaufgaben zu Endziffern.

Q: Was passiert, wenn der Exponent 0 oder der Modul 1 ist?

Bei e = 0 ist das Ergebnis 1 bmod m, was für jeden Modul außer m = 1 gleich 1 ist; bei m = 1 ist es 0, denn modulo 1 ist jede ganze Zahl kongruent zu 0. Diese Sonderfälle werden korrekt behandelt, und m = 1 liefert für jede Basis und jeden Exponenten 0 – mathematisch richtig, kein Fehler.

Q: Kann ich eine negative Basis oder einen negativen Exponenten verwenden?

Negative Basen sind unproblematisch: Der Rechner reduziert sie zuerst auf einen gleichwertigen positiven Rest, -12 verhält sich also wie m - 12. Negative Exponenten werden nicht unterstützt, denn sie würden das modulare Inverse der Basis erfordern, das nur existiert, wenn gcd(b, m) = 1. Umgehen lässt sich das, indem Sie zuerst b^-1 bmod m berechnen und dieses dann mit |e| potenzieren.

Q: Wie wird modulare Exponentiation in RSA und der Kryptografie eingesetzt?

RSA-Ver- und -Entschlüsselung bestehen jeweils aus einer einzigen modularen Exponentiation c = m^e bmod n mit einem Modul von 2048+ Bits – genau das berechnet die Methode „Quadrieren und Multiplizieren“ effizient. Der Diffie-Hellman-Schlüsselaustausch und ElGamal funktionieren nach demselben Prinzip. Die Laufzeit O(log e) macht riesige Exponenten praktikabel, während die Schwierigkeit, die Operation ohne den geheimen Schlüssel umzukehren, die Verfahren sicher hält.

Q: Was ist ein häufiger Fehler bei der Berechnung von b^e mod m?

Der häufigste Fehler ist, b^e zuerst auszurechnen und den Rest erst danach zu nehmen – die Potenz wird schnell astronomisch groß und lässt den Rechner überlaufen oder sich gar nicht mehr aufschreiben. Reduzieren Sie stattdessen immer nach jedem Quadrieren und Multiplizieren modulo m. Ein weiterer klassischer Lapsus: zu übersehen, dass b^0 bmod 1 = 0 und nicht 1 ist, weil modulo 1 alles kongruent zu 0 ist.

Aktualisiert: 14 Oktober 2026

Berechnet b^e mod m sofort – auch wenn der Exponent Hunderte von Stellen hat – mit schneller binärer Exponentiation (Quadrieren und Multiplizieren). Geben Sie eine Basis, einen nicht-negativen Exponenten und einen positiven Modul ein und verfolgen Sie optional jeden einzelnen Quadrierungsschritt.

Potenz modulo m berechnen

Formel für modulare Exponentiation

Formel

\[ c \;=\; b^e \bmod m \] \[ e = \sum_{k=0}^{n} e_k\,2^k \;\;\Longrightarrow\;\; b^e \;\equiv\; \prod_{k:\; e_k = 1} \bigl(b^{2^k} \bmod m\bigr) \pmod{m}, \qquad b^{2^k} \equiv \bigl(b^{2^{k-1}}\bigr)^2 \pmod{m} \]

Dabei ist:

\(b\) — die Basis (eine beliebige ganze Zahl)
\(e\) — der Exponent (eine nicht-negative ganze Zahl)
\(m\) — der Modul (eine positive ganze Zahl)
\(e_k\) — die Bits von \(e\) in seiner Binärdarstellung
\(c\) — das Ergebnis: der Rest von \(b^e\) bei der Division durch \(m\)

Die erste Zeile definiert die modulare Exponentiation. Die zweite Zeile ist die Identität der binären Exponentiation (Quadrieren und Multiplizieren), auf der der Rechner beruht: Der Exponent wird in Zweierpotenzen zerlegt, die Potenzen \(b^{2^k}\) werden durch wiederholtes Quadrieren bestimmt, und nur diejenigen mit gesetzten Bits werden multipliziert – alles modulo \(m\), sodass die Zwischenwerte nie ausufern.

Modulare Exponentiation – Rechenbeispiel

Beispiel: Berechnen Sie \(3^{644} \bmod 645\), die Vorgabewerte des Rechners. Die Zahl \(3^{644}\) hat 308 Stellen – die Potenz erst auszurechnen und danach zu reduzieren, ist also aussichtslos.

Schritt 1 – Basis reduzieren: \(3 \bmod 645 = 3\).

Schritt 2 – Exponent binär darstellen:

\[ 644 = 512 + 128 + 4 = 1010000100_2 \]

Wiederholtes Quadrieren modulo 645 liefert für die gesetzten Bits \(3^4 \equiv 81\), \(3^{128} \equiv 396\) und \(3^{512} \equiv 111 \pmod{645}\).

Schritt 3 – Diese Werte multiplizieren und dabei jedes Mal modulo 645 reduzieren:

\[ 3^{644} \equiv 81 \times 396 \times 111 \equiv 471 \times 111 \equiv 52281 \equiv 36 \pmod{645} \]

Ergebnis: \(3^{644} \bmod 645 = 36\). Der Algorithmus benötigt nur 9 Quadrierungen und 3 Multiplikationen – 12 modulare Operationen statt der 643, die ein naives Vorgehen erfordern würde.

So benutzen Sie den Rechner

Geben Sie die Basis (b) ein – eine beliebige ganze Zahl, positiv oder negativ.
Geben Sie den Exponenten (e) ein – eine nicht-negative ganze Zahl. Er darf so groß sein, dass sich \(b^e\) gar nicht direkt berechnen lässt; genau dafür ist dieses Werkzeug da.
Geben Sie den Modul (m) ein – eine beliebige positive ganze Zahl.
Lassen Sie das Häkchen bei Quadrierungsschritte anzeigen gesetzt, wenn Sie die Binärdarstellung des Exponenten und eine Tabelle aller Quadrierungsschritte sehen möchten; entfernen Sie es für eine schlichte Antwort.
Lesen Sie das Ergebnis (bᵉ mod m), die reduzierte Basis (b mod m) sowie die schrittweise Herleitung ab.

Was ist modulare Exponentiation?

Die modulare Exponentiation beantwortet die Frage: Welcher Rest bleibt, wenn \(b^e\) durch \(m\) geteilt wird? Das Ergebnis liegt immer zwischen \(0\) und \(m-1\). Es ist also die Zahl \(c\) mit \(0 \le c < m\), für die \(b^e \equiv c \pmod{m}\) gilt. So bedeutet zum Beispiel \(3^{644} \bmod 645 = 36\), dass \(3^{644}\) bei der Division durch 645 den Rest 36 lässt.

Der naive Weg – erst \(b^e\) ausrechnen, dann den Rest nehmen – scheitert schnell. \(3^{644}\) hat bereits 308 Stellen, und in der Kryptografie sind Exponenten mit Hunderten von Stellen Alltag; \(b^e\) hätte dort mehr Stellen, als es Atome im Universum gibt. Die Lösung ist die Methode „Quadrieren und Multiplizieren“: Den Exponenten binär schreiben, \(b^{2^k} \bmod m\) durch wiederholtes Quadrieren und Reduzieren bestimmen und anschließend nur die Werte zu den gesetzten Bits multiplizieren. Das erfordert lediglich \(O(\log e)\) modulare Multiplikationen statt \(e-1\), und weil jeder Zwischenwert modulo \(m\) reduziert wird, wächst keine Zahl über etwa \(m^2\) hinaus.

Die modulare Exponentiation ist das Arbeitstier der Public-Key-Kryptografie. RSA-Ver- und -Entschlüsselung bestehen jeweils aus einer einzigen modularen Exponentiation mit riesigem Modul; auch der Diffie-Hellman-Schlüsselaustausch und das ElGamal-Verfahren beruhen darauf. Zudem treibt sie Primzahltests wie den Fermat-Test und den Miller-Rabin-Test an, die prüfen, ob \(a^{n-1} \equiv 1 \pmod n\) gilt – die dahinterstehende Zahlentheorie können Sie mit unseren Rechnern zum Kleinen Satz von Fermat und zum Satz von Euler erkunden.

Die Schrittanzeige macht den Algorithmus durchschaubar: Die Tabelle führt jede Bitposition \(k\) des Exponenten neben \(b^{2^k} \bmod m\) auf, die hervorgehobenen Zeilen sind die tatsächlich verwendeten, und deren Produkt (reduziert modulo \(m\)) ist Ihr Ergebnis. Genau das geschieht intern auch in Computeralgebrasystemen – und wer es einmal gesehen hat, versteht, warum riesige Exponenten kein Problem sind.

Voraussetzungen, Grenzen und Tipps

Der Exponent muss nicht-negativ sein. Ein negativer Exponent würde das modulare Inverse von \(b\) erfordern, das nur existiert, wenn \(\gcd(b, m) = 1\). Berechnen Sie in diesem Fall zunächst das Inverse mit unserem Rechner für das multiplikative Inverse modulo m und verwenden Sie dessen Ausgabe anschließend als Basis mit positivem Exponenten.
Der Modul muss positiv sein. Bei \(m = 1\) ist jede ganze Zahl kongruent zu 0, das Ergebnis ist also 0 – das ist mathematisch korrekt, kein Fehler.
Negative Basen sind unproblematisch. Die Basis wird zunächst auf ihren kleinsten nicht-negativen Rest \(b \bmod m\) reduziert; \(-12\) und \(m - 12\) liefern daher dasselbe Ergebnis.
Exponent 0 ergibt \(1 \bmod m\) (nur bei \(m = 1\) ist das 0), im Einklang mit \(b^0 = 1\).
Größenbeschränkungen: Basis und Modul dürfen jeweils bis zu 1000 Stellen haben, der Exponent darf bis zu \(10^{18}\) betragen. Da der Algorithmus im Exponenten logarithmisch ist, geht selbst das in einem Augenblick.
Ergebnisse auf anderem Weg prüfen: Bei einem zusammengesetzten Modul können Sie die Berechnung in Primzahlpotenz-Anteile zerlegen und wieder zusammenfügen – probieren Sie unseren Rechner zum Chinesischen Restsatz, um Ergebnisse unabhängig zu überprüfen.

Häufig gestellte Fragen

Wie berechne ich eine Potenz modulo m von Hand?

Mit der Methode „Quadrieren und Multiplizieren“. Reduzieren Sie zuerst die Basis: Ersetzen Sie b durch \(b \bmod m\). Schreiben Sie dann den Exponenten binär und quadrieren Sie die Basis wiederholt, wobei Sie nach jedem Schritt modulo m reduzieren: \(b^2, b^4, b^8, b^{16}, \ldots\). Multiplizieren Sie schließlich nur die Quadrate, die zu den 1-Bits des Exponenten gehören, und reduzieren Sie dabei jedes Mal modulo m. So bleibt jeder Zwischenwert unter \(m^2\).

Warum liegt das Ergebnis von b^e mod m immer zwischen 0 und m-1?

Weil die modulare Arithmetik mit kleinsten nicht-negativen Resten arbeitet. Der Ausdruck \(b^e \bmod m\) ist definiert als der Rest bei der Division von \(b^e\) durch \(m\), und Divisionsreste erfüllen stets \(0 \le c \le m-1\). Auch eine negative Basis wird zunächst in den zugehörigen positiven Rest umgewandelt, das Ergebnis ist also nie negativ.

Wie finde ich die letzte Ziffer einer großen Potenz (z. B. 7^100)?

Das ist eine modulare Exponentiation im Gewande: Die letzte Ziffer einer Zahl ist diese Zahl modulo 10. Berechnen Sie also hier \(7^{100} \bmod 10\). Ebenso sind die letzten beiden Ziffern der Wert modulo 100 und die letzten drei Ziffern der Wert modulo 1000. Ein klassischer Kniff bei Wettbewerbs- und Hausaufgaben zu Endziffern.

Was passiert, wenn der Exponent 0 oder der Modul 1 ist?

Bei \(e = 0\) ist das Ergebnis \(1 \bmod m\), was für jeden Modul außer \(m = 1\) gleich 1 ist; bei \(m = 1\) ist es 0, denn modulo 1 ist jede ganze Zahl kongruent zu 0. Diese Sonderfälle werden korrekt behandelt, und \(m = 1\) liefert für jede Basis und jeden Exponenten 0 – mathematisch richtig, kein Fehler.

Kann ich eine negative Basis oder einen negativen Exponenten verwenden?

Negative Basen sind unproblematisch: Der Rechner reduziert sie zuerst auf einen gleichwertigen positiven Rest, \(-12\) verhält sich also wie \(m - 12\). Negative Exponenten werden nicht unterstützt, denn sie würden das modulare Inverse der Basis erfordern, das nur existiert, wenn \(\gcd(b, m) = 1\). Umgehen lässt sich das, indem Sie zuerst \(b^{-1} \bmod m\) berechnen und dieses dann mit \(|e|\) potenzieren.

Wie wird modulare Exponentiation in RSA und der Kryptografie eingesetzt?

RSA-Ver- und -Entschlüsselung bestehen jeweils aus einer einzigen modularen Exponentiation \(c = m^e \bmod n\) mit einem Modul von 2048+ Bits – genau das berechnet die Methode „Quadrieren und Multiplizieren“ effizient. Der Diffie-Hellman-Schlüsselaustausch und ElGamal funktionieren nach demselben Prinzip. Die Laufzeit \(O(\log e)\) macht riesige Exponenten praktikabel, während die Schwierigkeit, die Operation ohne den geheimen Schlüssel umzukehren, die Verfahren sicher hält.

Was ist ein häufiger Fehler bei der Berechnung von b^e mod m?

Der häufigste Fehler ist, \(b^e\) zuerst auszurechnen und den Rest erst danach zu nehmen – die Potenz wird schnell astronomisch groß und lässt den Rechner überlaufen oder sich gar nicht mehr aufschreiben. Reduzieren Sie stattdessen immer nach jedem Quadrieren und Multiplizieren modulo m. Ein weiterer klassischer Lapsus: zu übersehen, dass \(b^0 \bmod 1 = 0\) und nicht 1 ist, weil modulo 1 alles kongruent zu 0 ist.