Berechnen Sie die modulare Exponentiation xy mod n sofort. Geben Sie die Basis, den Exponenten und den Modulus ein, um den Rest effizient mit dem Algorithmus der binären Exponentiation zu bestimmen.
Rechner für modulare Exponentiation
So verwenden Sie den Rechner
- Geben Sie im Feld x (Basis) die Basis als ganze Zahl ein.
- Geben Sie im Feld y (Exponent) einen nichtnegativen ganzzahligen Exponenten ein.
- Geben Sie im Feld n (Modulus) einen positiven ganzzahligen Modulus ein (n ≥ 1).
- Wählen Sie Berechnen. Der Wert von xy mod n erscheint im Feld Ergebnis.
- Für eine neue Rechnung wählen Sie Löschen.
Was ist modulare Exponentiation?
Modulare Exponentiation berechnet den Rest, der bei der Division von xy durch n entsteht:
xy mod n = r
Dabei ist r der Rest der Division von xy durch n, wobei 0 ≤ r < n gilt.
Diese Operation ist grundlegend für die Zahlentheorie und Public-Key-Kryptografie (einschließlich RSA), bei der sehr große Potenzen effizient ausgewertet werden müssen.
Schnelle modulare Exponentiation
Die direkte Berechnung von xy wird bei großen Exponenten unpraktikabel. Der Algorithmus der binären Exponentiation löst das Problem in O(log y) Operationen durch wiederholtes Quadrieren der Basis:
- Wenn y gerade ist: xy = (xy/2)2
- Wenn y ungerade ist: xy = x × xy−1
Der Modulus wird in jedem Schritt angewendet, sodass die Zwischenwerte klein bleiben.
Beispiele zur modularen Exponentiation
| x (Basis) | y (Exponent) | n (Modulus) | xy mod n |
|---|---|---|---|
| 2 | 10 | 7 | 2 |
| 3 | 4 | 5 | 1 |
| 5 | 3 | 13 | 8 |
| 7 | 0 | 10 | 1 |
| 2 | 100 | 1000000007 | 976371285 |
Häufig gestellte Fragen
Was ist modulare Exponentiation?
Die modulare Exponentiation berechnet xy mod n, also den Rest bei der Division von xy durch n. Sie ist grundlegend für Kryptografie und Zahlentheorie.
Wie berechne ich xy mod n?
Geben Sie Basis x, Exponent y und Modulus n ein und wählen Sie Berechnen. Das Ergebnis ist der Rest bei der Division von xy durch n, effizient berechnet mit schneller modularer Exponentiation.
Warum wird modulare Exponentiation in der Kryptografie verwendet?
Die modulare Exponentiation bildet die Grundlage von RSA und des Diffie-Hellman-Protokolls. Vorwärts ist sie effizient, wegen des diskreten Logarithmus jedoch äußerst schwer umzukehren – eine nützliche Asymmetrie für die digitale Sicherheit.
Was ist 2¹⁰ mod 7?
2¹⁰ = 1024 und 1024 = 146 × 7 + 2. Daher gilt 2¹⁰ mod 7 = 2.
Was ist der Algorithmus der binären Exponentiation?
Dabei wird xy mod n effizient berechnet, indem der Exponent wiederholt halbiert wird. Die Zahl der Operationen sinkt von O(y) auf O(log y), sodass selbst enorme Potenzen in Sekundenbruchteilen verarbeitet werden können.
Verwandte Rechner und Anleitungen
