Modular Exponentiation (PowMod)

Rechner und Formel zur Berechnung der Modular Exponentiation (PowMod)

Modular Exponentiation Rechner

Was wird berechnet?

Diese Funktion liefert das Resultat der Modular Exponentiation (PowMod). Das Ergebnis ist der Rest einer Division von b^e durch m, berechnet als (b^e) mod m.

Eingabewerte




Ergebnis
Das Ergebnis ist der Rest der Division b^e ÷ m

Modular Exponentiation Info

Eigenschaften

Modular Exponentiation:

  • Berechnet (b^e) mod m effizient
  • Vermeidet große Zwischenergebnisse
  • Ergebnis liegt immer zwischen 0 und m-1
  • Wichtig in der Kryptographie

Wichtig: Die Basis b und der Modulo m müssen positive ganze Zahlen sein. Der Exponent e kann auch 0 sein.

Beispiele
3² mod 5 = 4
9 mod 5 = 4
2³ mod 7 = 1
8 mod 7 = 1
5⁴ mod 11 = 9
625 mod 11 = 9
7⁰ mod 10 = 1
Jede Zahl hoch 0 ist 1
Anwendungen
  • RSA-Verschlüsselung
  • Diffie-Hellman-Schlüsselaustausch
  • Digitale Signaturen
  • Pseudozufallszahlen

Formeln der Modular Exponentiation

Grundformel
\[x = b^e \bmod m\] Modular Exponentiation
Äquivalente Form
\[x = (b^e) \bmod m\] Rest der Division
Multiplikationsregel
\[(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m\] Produkt modulo m
Potenzregel
\[a^{x+y} \bmod m = (a^x \bmod m \cdot a^y \bmod m) \bmod m\] Exponentenaddition
Fermats kleiner Satz
\[a^{p-1} \equiv 1 \pmod{p}\] Für Primzahl p und gcd(a,p) = 1
Eulers Theorem
\[a^{\phi(n)} \equiv 1 \pmod{n}\] Für gcd(a,n) = 1

Rechenbeispiel

Beispiel: 4² mod 10 berechnen

Gegeben:

  • Basis b = 4
  • Exponent e = 2
  • Modulo m = 10

Berechnung:

\[4^2 \bmod 10 = 16 \bmod 10 = 6\]

Ergebnis: Der Rest von 16 ÷ 10 ist 6.

RSA-Verschlüsselung Beispiel

Vereinfachtes RSA-Beispiel

RSA-Parameter:

  • p = 3, q = 11 (Primzahlen)
  • n = p·q = 33
  • φ(n) = (p-1)·(q-1) = 20
  • e = 3 (öffentlicher Exponent)

Verschlüsselung von m = 4:

\[c = m^e \bmod n\] \[c = 4^3 \bmod 33 = 64 \bmod 33 = 31\]

Ergebnis: Die Nachricht 4 wird zu 31 verschlüsselt.

Schnelle Exponentiation

Beispiel: 5¹³ mod 13 mit binärer Methode

Binäre Darstellung:

13 = 1101₂ = 8 + 4 + 1

5¹³ = 5⁸ · 5⁴ · 5¹

Schrittweise Berechnung:

5¹ mod 13 = 5
5² mod 13 = 12
5⁴ mod 13 = 1
5⁸ mod 13 = 1
5¹³ mod 13 = 1·1·5 = 5

Vorteil: Nur log₂(13) ≈ 4 Multiplikationen statt 12.

Definition und Anwendungen

Was ist Modular Exponentiation?

Modular Exponentiation berechnet (b^e) mod m effizient, ohne die oft sehr große Zahl b^e explizit zu berechnen. Dies ist essentiell für kryptographische Anwendungen, wo große Zahlen verwendet werden.

Kryptographische Bedeutung

In der modernen Kryptographie ist modular Exponentiation die Grundlage für: RSA-Verschlüsselung, Diffie-Hellman-Schlüsselaustausch, digitale Signaturen und viele andere Sicherheitsverfahren.

Algorithmische Effizienz
  • Naive Methode: O(e) Multiplikationen
  • Binäre Methode: O(log e) Multiplikationen
  • Speicherplatzvorteil: Keine großen Zwischenergebnisse
  • Praktisch: Auch für riesige Exponenten verwendbar

Ist diese Seite hilfreich?            
Vielen Dank für Ihr Feedback!

Das tut uns leid

Wie können wir die Seite verbessern?

Logarithmus und Exponenten

Log, Logarithmus zur Basis 10  •  Ln, Logarithmus zur Basis e  •  Logarithmus zur Basis a (Loga)  •  Exponential Funktion Basis 10x  •  Exponential Funktion Basis ex  •  Exponential Funktion Basis xy  •  Quadratwurzel  •  Kubikwurzel  •  N-te Wurzel  •  PowMod, Modular Exponentiation  •  Hypot  •