In der Kryptographie werden bei allen modernen asymmetrischen Verfahren
große modulare Potenzen benutzt; oft sind dabei sowohl die Basis als auch
Exponent und Modulus Zahlen mit mehreren hundert oder tausend Dezimalstellen.
Bei solchen Zahlen ist es natürlich nicht mehr möglich, mit dem naiven Ansatz
zu arbeiten, der das Potenzieren auf eine Reihe Multiplikationen zurückführt.
Stattdessen wird hier ein anderes Verfahren verwendet, das mit wesentlich
weniger Operationen auskommt (Größenordnung log2(exponent)).
Zur Berechnung wird zunächst der Exponent in Binärform dargestellt und die Potenz dann als Reihe von Faktoren dargestellt. Der erste Faktor ist gleich der Basis; die weiteren Faktoren ergeben sich jeweils durch Quadrieren des vorhergehenden Faktors. Wenn ein Bit des Exponenten 1 ist, wird das Ergebnis mit dem jeweiligen Faktor multipliziert; falls das Bit 0 ist, wird es nicht verändert.
Nach jedem Quadrieren und jeder Multiplikation wird eine Modulo-Operation ausgeführt. Diese Operation hat keinen Einfluß auf das Endergebnis; sie dient nur dazu, die Größe der Zwischenergebnisse zu reduzieren.
Diese Seite erlaubt eine Berechnung modularer Potenzen mit einem Maximalwert für Basis, Exponent und Modulus von jeweils 9223372036854775807 (263 - 1).
279 mod 101 = 42
279 mod 101 = 42