Rechner für modulare Exponentiation

Berechnen Sie Basis^Exponent mod Modul.

Ergebnis

3

So wird gerechnet

Das Tool berechnet BasisExp mod m, den Rest, der bei der Division von BasisExp durch m bleibt, mit dem Verfahren „Quadrieren und Multiplizieren“. Es geht die Binärziffern des Exponenten durch: Die laufende Basis wird jedes Mal quadriert (nach jedem Quadrieren wird der Rest gebildet) und mit dem Ergebnis multipliziert, wenn die aktuelle Binärziffer 1 ist. So bleibt jede Zwischenzahl unter m2, und gewaltige Potenzen müssen nie ausgeschrieben werden. Alle Eingaben werden auf ganze Zahlen abgeschnitten, der Modul muss mindestens 1 sein, und der Exponent darf nicht negativ sein. Eine negative Basis wird zuerst in den Bereich 0 bis m−1 gebracht.

Rechenbeispiel

Gesucht ist 7128 mod 13. Quadrieren Sie wiederholt und reduzieren Sie jedes Mal mod 13: 72 = 49 ergibt 10; 74 = 100 ergibt 9; 78 = 81 ergibt 3; 716 = 9 ergibt 9; und so weiter. Da 128 eine Zweierpotenz ist, sind über die abschließende Quadrierkette hinaus keine weiteren Multiplikationen nötig. Der Rest ist 3, ohne dass je die 109-stellige Zahl 7128 berechnet werden muss.

Dieses Beispiel ausprobieren →

Häufige Fehler

  • Zuerst die volle Potenz berechnen und dann den Rest bilden; bei großen Exponenten läuft die Zahl über oder verliert an Genauigkeit.
  • Einen negativen Exponenten eingeben; ein modulares Inverses ist eine andere Operation, und das Tool liefert kein Ergebnis.
  • Einen Modul von 0 oder weniger verwenden; eine Division durch null hat keinen Rest.
  • Erwarten, dass Nachkommastellen bei Basis oder Exponent berücksichtigt werden; sie werden auf ganze Zahlen abgeschnitten.

Quellen

Über diesen Rechner

Dieser Rechner berechnet die modulare Exponentiation – Basis^Exponent mod Modul – mit dem schnellen Verfahren „Quadrieren und Multiplizieren“, statt zuerst die volle Potenz zu berechnen; so bleiben die Zahlen selbst bei riesigen Exponenten handhabbar.

Sie ist die Kernoperation der Public-Key-Kryptografie: RSA-Verschlüsselung, Diffie-Hellman-Schlüsselaustausch und digitale Signaturen potenzieren allesamt wiederholt Zahlen mit großen Exponenten modulo einer großen Zahl. Informatikstudierende nutzen sie, um den Algorithmus zu lernen, und Entwickler, um Ergebnisse bei der Implementierung von Kryptografiecode zu überprüfen.

War das hilfreich?

Sie können bis zu 3 Reaktionen auswählen.

Kommentare

  • Schreiben Sie den ersten Kommentar.

Beliebte Rechner

Alle Rechner