Modulare Potenzierung
Dieser Online-Rechner führt modulare Potenzierung von großen Ganzzahlen durch.
Dieser Online-Rechner führt die Potenzierung einer großen Ganzzahl über ein Modul durch. Ein schneller Algorithmus wird dafür verwendet, dessen Beschreibung unter dem Rechner gefunden werden kann.
Modulare Potenzierung
Schnelle Potenzierungsalgorithmen
Die einfachste Durchführung einer Potenzierung benötigt eine N-1 Multiplikationsoperation, wobei N die Exponent Base ist. Trotz der Leistungen von modernen Computern, passt dieses Verfahren hier nicht, da Zahlen für den Exponent verwendet werden, die sogar größer als die Standard 64-Bit Ganzzahlen. Zum Beispiel die Mersenne-Primzahl: 618970019642690137449562111 als Standardwert hat einen Exponentswert von 89 Bits (siehe Bitlänge).
Um daher mit solch Exponenten zu arbeiten, benötigt man schnelle Potenzierungsalgorithmen.
In dem Polynomische Leistungsentwicklung Rechner wird ein schneller Potenzierungsalgorithmus basierend auf eine Potenzbaum bereits verwendet. Er erlaubt es, die Zahl der Multiplikation zu minimisieren. Jedoch kann er nicht für riesige Exponenten genutzt werden, da der Potenzierungsbaum zu viel Speicher konsumieren würde.
Dieser Rechner nutzt die bigInt Bibliothek Ausführung des schnellen modularen Potenzierungsalgorithmus , basierend auf die binäre Methode. Der gleiche Artikel beschreibt eine Version des Algorithmus, der binäre Ziffern vom am signifikantesten zu dem am wenigsten signifikanten Teil verarbeitet (von links nach rechts). Dies ist für diesen Fall jedoch ungünstig, da man hier mit einer Ganzzahl mit variabler Länge arbeitet, und daher die Position des am signifikantesten Bit nicht vorher kennt.
Binärer Potenzierungsalgorithmus (rechts nach links).
Der Algorithmus, den wir nutzen, bearbeitet den Exponenten-Bits vom am wenigsten signifikanten zu dem am signifikantesten (von rechts nach links).
Dies ist der Algorithmus Pseudocode:
a //base
e //exponent
m //modulus
//modular exponentiation
r ⟵ 1
while (e!=0) {
if (e mod 2 = 1) r ⟵ r * a mod m;
e ⟵ e / 2;
a = a*a mod m;
}
output ⟵ r
Kommentare