Warum nicht einfach a^b berechnen und dann mod nehmen?

Für große Exponenten hat die Zahl a^b astronomisch viele Ziffern — weit mehr, als ein Computer speichern kann. Der Square-and-Multiply-Algorithmus hält Zwischenwerte klein, indem er bei jedem Multiplikationsschritt modulo m rechnet.

ⁿ

Modulare-Exponentiation-Rechner

Square-and-Multiply · BigInt Support · RSA · Diffie-Hellman

Berechne a^b mod m für beliebig große ganze Zahlen mit dem schnellen binären (rechts-nach-links) Algorithmus. Vollständige Schritt-für-Schritt-Tabelle, Binärvisualisierung und kryptografische Anwendungen.

Schnellbeispiele

Basis (a)

Exponent (b)

Modulus (m > 1)

a^b mod m

—

Endergebnis

b in Binär

—

Binärdarstellung

Quadrierungen

—

⌊log₂ b⌋ Schritte

Multiplikationen

—

popcount(b) − 1

Binärdarstellung von b

Grün = Bit 1 (Multiplizieren & Quadrieren). Grau = Bit 0 (nur Quadrieren). LSB links, MSB rechts. Begrenzt auf 32 Bits.

Übersicht des Algorithmus

...

Schritt-für-Schritt-Quadrierungstabelle

Spalten verarbeitet LSB nach MSB von b. Grüne Zeilen: Bit = 1, Multiplikation auf das Ergebnis angewendet. Graue Zeilen: Bit = 0, nur Quadrierung.

Schritt	Bit (LSB→MSB)	Aktuelle Basis a^{2^k} mod m	Ergebnis	Operation

🔒

RSA Verschlüsselung & Entschlüsselung

Public-Key-Kryptografie durch modulare Exponentiation

RSA verschlüsselt eine Nachricht M als C = M^e mod n mit dem öffentlichen Schlüssel (e, n). Die Entschlüsselung stellt M als M = C^d mod n mit dem privaten Exponenten d wieder her.

Toy RSA example (p=11, q=13, n=143): φ(n) = (p-1)(q-1) = 10×12 = 120 Public exponent: e = 7 (gcd(7,120)=1) Private exponent: d = 103 (7×103 = 721 = 6×120+1 ≡ 1 mod 120) Encrypt M=2: C = 2^7 mod 143 = 128 Decrypt C=128: M = 128^103 mod 143 = 2 ✓

Probiere es aus: Verwende das Schnellbeispiel "2¹⁰³ mod 143 (toy RSA)" im Rechner.

🔑

Diffie-Hellman-Schlüsselaustausch

Gemeinsames Geheimnis über unsicheren Kanal

Alice und Bob einigen sich auf eine Primzahl p und einen Generator g. Alice berechnet A = g^a mod p und Bob berechnet B = g^b mod p. Der gemeinsame Schlüssel ist K = g^ab mod p.

Example: p=23, g=5 Alice's secret a=6: A = 5^6 mod 23 = 8 Bob's secret b=15: B = 5^15 mod 23 = 19 Shared key (Alice): K = B^a mod p = 19^6 mod 23 = 2 Shared key (Bob): K = A^b mod p = 8^15 mod 23 = 2 ✓

Sicherheit: a aus A = g^a mod p zu finden, ist das diskrete Logarithmus-Problem — rechnerisch schwer für große p.

𝕧

Fermat-Primzahltest

Wahrscheinlichkeitstheoretische Primzahlerkennung durch modulare Exponentiation

Fermats kleiner Satz: Wenn p eine Primzahl ist und ggT(a, p) = 1, dann a^p-1 ≡ 1 (mod p). Ein Fermat-Primzahltest prüft diese Bedingung für mehrere zufällige Basen.

Test p=17 for primality: Choose a=3: 3^16 mod 17 = 1 ✓ (consistent with prime) Choose a=5: 5^16 mod 17 = 1 ✓ (consistent with prime) Test p=15 (composite) with a=2: 2^14 mod 15 = 4 ≠ 1 → 15 is NOT prime ✓

Was ist modulare Exponentiation?

Modulare Exponentiation ist die Berechnung von a^b mod m — das Potenzieren einer Basis a mit einem Exponenten b und das Behalten nur des Rests bei der Division durch den Modulo m. Diese Operation ist ein Eckpfeiler der modernen Zahlentheorie und Public-Key-Kryptografie.

Zum Beispiel 3⁶⁴⁴ mod 645 = 36. Während der Zwischenwert 3⁶⁴⁴ eine astronomisch große Zahl ist, ist die Antwort einfach 36.

Warum die naive Berechnung versagt

Der direkte Ansatz — zuerst a^b berechnen, dann den Rest nehmen — ist für große Exponenten völlig unpraktisch. Die Zahl 2¹⁰⁰⁰ hat bereits über 300 Dezimalstellen.

Die wichtigste Erkenntnis ist, dass wir nach jeder einzelnen Multiplikation modulo m reduzieren können, wodurch alle Zwischenwerte unter m² bleiben.

Der Square-and-Multiply-Algorithmus

The algorithm processes the Binärdarstellung of b from LSB (least significant bit) to MSB. At step k (corresponding to bit k of b):

Immer quadrieren: berechne basis = basis × basis mod m
Wenn Bit k = 1: multipliziere zusätzlich ergebnis = ergebnis × basis mod m
Wenn Bit k = 0: überspringe die Multiplikation

Das Ergebnis akkumuliert nur jene Potenzen von a, deren entsprechendes Bit in b 1 ist.

O(log b) Komplexität

Der Algorithmus führt genau ⌊log₂ b⌋ Quadrierungen durch. Da die Anzahl O(log b) ist, ist die Gesamtzahl der modularen Multiplikationen O(log b).

Für 2048-Bit-RSA-Parameter bedeutet dies etwa 2000 Multiplikationen von 2048-Bit-Zahlen — in Millisekunden machbar.

RSA-Verschlüsselung und -Entschlüsselung

RSA ist das am weitesten verbreitete Public-Key-Kryptosystem. Die Schlüsselerzeugung wählt zwei große Primzahlen p und q.

Verschlüsselung: C = M^e mod n
Entschlüsselung: M = C^d mod n

Beide Operationen sind reine modulare Exponentiationen.

Diffie-Hellman-Schlüsselaustausch

Zwei Parteien einigen sich öffentlich auf eine große Primzahl p und eine Primitivwurzel g. Jede Partei wählt einen privaten Zufallsexponenten und veröffentlicht ihren öffentlichen Wert.

Fermats kleines Theorem

Fermats kleiner Satz besagt: Wenn p prim ist und ggT(a, p) = 1, dann a^p−1 ≡ 1 (mod p). Dies ist eine notwendige Bedingung für Primalität.

Referenztabelle: Beispielberechnungen

a	b	m	a^b mod m	b in Binär	Quadrierungen
3	644	645	36	1010000100	9
2	10	1000	24	1010	3
7	256	13	9	100000000	8
2	103	143	2	1100111	6
5	6	23	8	110	2
123	456	789	699	111001000	8

Häufig gestellte Fragen

Was ist modulare Exponentiation?

Modulare Exponentiation ist die Berechnung von a^b mod m. Das Ergebnis liegt immer im Bereich [0, m−1].

Warum nicht a^b berechnen und dann mod nehmen?

Für große Exponenten hat der Wert a^b Millionen von Stellen. Der Square-and-Multiply-Algorithmus reduziert modulo m nach jeder Multiplikation.

Wie funktioniert der Square-and-Multiply-Algorithmus?

Der Algorithmus tastet die binären Ziffern von b vom LSB zum MSB ab. In jedem Schritt k: (1) quadriere die aktuelle Basis mod m. (2) Wenn Bit k von b 1 ist, multipliziere das laufende Ergebnis mit der aktuellen Basis mod m.

Wie hoch ist die Zeitkomplexität der modularen Exponentiation?

Der Algorithmus verwendet O(log b) modulare Multiplikationen. Jede Multiplikation kostet O((log m)²) Bitoperationen, was eine Gesamtbitkomplexität von O(log b × (log m)²) ergibt.

Wie wird die modulare Exponentiation in RSA verwendet?

Die RSA-Verschlüsselung ist C = M^e mod n und die Entschlüsselung ist M = C^d mod n. Beide sind modulare Exponentiationen.

Was ist der kleine Satz von Fermat?

Fermats kleiner Satz besagt, dass wenn p prim ist und ggT(a, p) = 1, dann a^p−1 ≡ 1 (mod p). Dies ist die Grundlage des Fermat-Primzahltests.

Was ist der Diffie-Hellman-Schlüsselaustausch?

Diffie-Hellman (DH) ermöglicht es zwei Parteien, über einen öffentlichen Kanal ein gemeinsames Geheimnis zu erstellen. Beide einigen sich auf eine Primzahl p und einen Generator g.

Modulare-Exponentiation-Rechner

Binärdarstellung von b

Übersicht des Algorithmus

Fermats kleines Theorem - Prüfung

Schritt-für-Schritt-Quadrierungstabelle

RSA Verschlüsselung & Entschlüsselung

Diffie-Hellman-Schlüsselaustausch

Fermat-Primzahltest

Was ist modulare Exponentiation?

Warum die naive Berechnung versagt

Der Square-and-Multiply-Algorithmus

O(log b) Komplexität

RSA-Verschlüsselung und -Entschlüsselung

Diffie-Hellman-Schlüsselaustausch

Fermats kleines Theorem

Referenztabelle: Beispielberechnungen

Häufig gestellte Fragen

Ähnliche Rechner