Rechner für modulare Exponentiation
Berechne (Basis^Exponent) mod m schnell und exakt mittels binärer Exponentiation durch Quadrieren.
Computed with exponentiation by squaring
Wie funktioniert dieser Rechner?
Die modulare Exponentiation berechnet (Basis^Exponent) mod m. Statt die riesige Potenz direkt zu berechnen, verwendet sie binäre Exponentiation durch Quadrieren: bei jedem Schritt die Basis quadrieren und den Exponenten halbieren, bei gesetzten Bits in das Ergebnis multiplizieren und durchgehend modulo m reduzieren. Dies läuft in etwa log2(Exponent) Multiplikationen und bleibt mit großen Ganzzahlen exakt.
Formel
How this is calculated
Gib drei Ganzzahlen ein: die Basis b, einen nichtnegativen Exponenten e und einen positiven Modul m. Der Rechner liefert den Rest von b hoch e bei Division durch m. Das naive Berechnen von b^e zuerst würde bei großen Exponenten überlaufen, daher verwendet dieses Werkzeug Exponentiation durch Quadrieren (auch binäre Exponentiation genannt).
Der Algorithmus startet mit result = 1 und reduziert die Basis modulo m. Er durchläuft dann die Bits des Exponenten vom niederwertigsten zum höchstwertigen: wann immer das aktuelle Bit 1 ist, multipliziert er das laufende Ergebnis mit der aktuellen Basis (mod m), und bei jedem Schritt quadriert er die Basis (mod m) und verschiebt den Exponenten um ein Bit nach rechts. Da jedes Zwischenprodukt modulo m reduziert wird, bleiben die Zahlen klein und der Aufwand ist proportional zu log2(e) Multiplikationen statt e davon. Alle Berechnungen erfolgen mit JavaScript-BigInt, sodass die Ergebnisse unabhängig von der Größe exakt sind.
Annahmen und Sonderfälle: der Exponent muss eine ganze Zahl e >= 0 und der Modul eine positive Ganzzahl m > 0 sein (mod 0 ist undefiniert). Die Basis darf negativ sein; sie wird zuerst mit ((b mod m) + m) mod m in den Bereich 0..m-1 normalisiert, sodass der zurückgegebene Rest stets nichtnegativ ist. Bei e = 0 ist das Ergebnis 1 mod m. Bei m = 1 ist das Ergebnis stets 0.
Häufige Fragen
Bei großen Exponenten ist b^e astronomisch groß und langsam oder unmöglich zu speichern. Das Reduzieren modulo m bei jeder Multiplikation hält jeden Wert unter m und endet in etwa log2(e) Schritten.
Ja. Die Basis wird vor der Schleife mit ((b mod m) + m) mod m in 0..m-1 normalisiert, sodass eine negative Basis dennoch einen korrekten nichtnegativen Rest liefert.
Per Konvention ist b^0 = 1, sodass das Ergebnis 1 mod m ist (was 0 ist, wenn m = 1).
Auch bekannt als
TG we-Calculate Editorial Team. (2026). Rechner für modulare Exponentiation [Online calculator]. TG we-Calculate. https://we-calculate.com/de/calculator/modular-exponentiation-calculator
TG we-Calculate Editorial Team. "Rechner für modulare Exponentiation." TG we-Calculate. 2026. https://we-calculate.com/de/calculator/modular-exponentiation-calculator.
TG we-Calculate Editorial Team, "Rechner für modulare Exponentiation," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/de/calculator/modular-exponentiation-calculator
@misc{wecalculate_modular_exponentiation_calculator, title = {Rechner für modulare Exponentiation}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/de/calculator/modular-exponentiation-calculator}}, year = {2026}, note = {TG we-Calculate} }
Hat Ihnen dieser Rechner geholfen?