Rechner für modulare Exponentiation
Berechne a hoch b modulo m, selbst wenn die Zahlen Hunderte Stellen haben. Der Rechner nutzt exakte BigInt-Arithmetik und das Square-and-Multiply-Verfahren und listet jeden Schritt mit den Binärziffern des Exponenten auf.
Zuletzt aktualisiert:
Ganze Zahl, darf negativ sein. Ausdrücke wie 2^64 funktionieren.
Ganze Zahl; ein negativer Wert nutzt das modulare Inverse
Ganze Zahl ≥ 1, z. B. 1000000007 oder 2^127-1
Anleitung: Rechner für modulare Exponentiation
- Gib die Basis a ein, z. B. einen Nachrichtenwert bei RSA.
- Gib den Exponenten b ein; er darf riesig sein, etwa 10^18.
- Gib den Modulus m ein, z. B. 3233 oder 10^9+7.
- Klicke auf Berechnen, um a^b mod m zu erhalten.
- Sieh dir die Tabelle an, um jede Quadrierung und Multiplikation nachzuvollziehen.
Rechenbeispiel: 3^13 mod 7 per Square-and-Multiply
13 ist binär 1101₂ (8 + 4 + 1). Quadriere die Basis in jedem Schritt und multipliziere, wenn das Bit 1 ist, wobei jedes Mal mod 7 reduziert wird:
| Bit (von rechts nach links) | Basispotenz mod 7 | Bit | Laufendes Ergebnis |
|---|---|---|---|
| 0 | 3¹ ≡ 3 | 1 | 1 × 3 = 3 |
| 1 | 3² ≡ 9 ≡ 2 | 0 | 3 |
| 2 | 3⁴ ≡ 2² ≡ 4 | 1 | 3 × 4 = 12 ≡ 5 |
| 3 | 3⁸ ≡ 4² = 16 ≡ 2 | 1 | 5 × 2 = 10 ≡ 3 |
Also ist 3^13 mod 7 = 3, gefunden mit 3 Quadrierungen und 3 Multiplikationen. Probe mit dem kleinen fermatschen Satz: 7 ist eine Primzahl, also 3^13 ≡ 3^(13 mod 6) = 3^1 = 3 ✓.
Nützliche Regeln
- Produktregel: (x × y) mod m = ((x mod m) × (y mod m)) mod m – deshalb ist das Reduzieren in jedem Schritt unbedenklich.
- Fermat: Ist p eine Primzahl und teilt p nicht a, gilt a^(p−1) ≡ 1 (mod p), also lässt sich b mod p − 1 reduzieren.
- Euler: Allgemeiner gilt: Ist ggT(a, m) = 1, dann a^φ(m) ≡ 1 (mod m), wobei φ die eulersche Phi-Funktion ist.
- Aufwand: Square-and-Multiply braucht höchstens 2·log₂(b) modulare Multiplikationen, sodass selbst ein 2048-Bit-Exponent nur ein paar Tausend Schritte benötigt.
- Übliche Moduln bei Programmierwettbewerben sind 10^9 + 7 und 998,244,353, beides Primzahlen.
Häufige Fragen
Was ist modulare Exponentiation?
Dabei berechnet man den Rest, wenn a^b durch m geteilt wird, geschrieben a^b mod m. Zum Beispiel 3^4 mod 5 = 81 mod 5 = 1. Sie ist eine Kernoperation bei RSA, Diffie–Hellman, Primzahltests und Hashing.
Warum berechnet man nicht einfach a^b und nimmt dann den Rest?
a^b wird astronomisch groß: 2^(10^18) hat etwa 3 × 10^17 Stellen. Wenn man nach jeder Multiplikation mod m reduziert, bleibt jede Zahl unter m², und die Identität (x·y) mod m = ((x mod m)(y mod m)) mod m garantiert dasselbe Endergebnis.
Wie funktioniert Square-and-Multiply?
Schreibe b binär. Quadriere die Basis wiederholt (a, a², a⁴, a⁸, … alle mod m) und multipliziere die Potenzen, deren Bit 1 ist, ins Ergebnis. 3^13 nutzt 13 = 1101₂, also 3^13 = 3^8 · 3^4 · 3^1. Das braucht etwa log₂(b) Schritte statt b − 1 Multiplikationen.
Wie wird sie bei RSA verwendet?
Die Verschlüsselung berechnet c = m^e mod n, die Entschlüsselung m = c^d mod n. Mit dem Lehrbuchschlüssel n = 3233, e = 17, d = 2753 wird die Nachricht 65 zu 65^17 mod 3233 = 2790 verschlüsselt, und 2790^2753 mod 3233 ergibt wieder 65.
Was bedeutet ein negativer Exponent in der modularen Arithmetik?
a^(−k) mod m bedeutet (a⁻¹)^k mod m, wobei a⁻¹ das modulare Inverse ist. Es existiert nur, wenn ggT(a, m) = 1. Zum Beispiel 7^(−1) mod 26 = 15, da 7 × 15 = 105 = 4 × 26 + 1.
Was ist der kleine fermatsche Satz?
Ist p eine Primzahl und a kein Vielfaches von p, dann gilt a^(p − 1) ≡ 1 (mod p). Exponenten lassen sich also mod p − 1 reduzieren: 3^200 mod 13 = 3^(200 mod 12) mod 13 = 3^8 mod 13 = 9. Der Rechner zeigt diese Abkürzung immer an, wenn der Modulus eine Primzahl ist.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.