Mein Problem ist zu berechnen(g^x) mod p schnell in JavaScript, wo^ ist Potenzierung,mod ist die Modulo-Operation. Alle Eingaben sind nichtnegative Ganzzahlen.x hat ungefähr 256 Bits undp ist eine Primzahl von 2048 Bits undg kann bis zu 2048 Bit haben.

Die meisten Programme, die ich in JavaScript gefunden habe, verwenden anscheinend die JavaScript BigInt-Bibliothek (http://www.leemon.com/crypto/BigInt.html). Das Ausführen einer einzelnen Exponentiation dieser Größe mit dieser Bibliothek dauert in meinem langsamen Browser (Firefox 3.0 mit SpiderMonkey) ungefähr 9 Sekunden. Ich suche nach einer Lösung, die mindestens 10-mal schneller ist. Die naheliegende Idee der Verwendung von Quadrat-und-Multiplikation (Potenzierung durch Quadrieren,http://en.wikipedia.org/wiki/Exponentiation_by_squaring) ist für 2048-Bit-Zahlen zu langsam: Es werden bis zu 4096 Multiplikationen benötigt.

Ein Upgrade des Browsers ist keine Option. Die Verwendung einer anderen Programmiersprache ist keine Option. Das Senden der Nummern an einen Webdienst ist keine Option.

Gibt es eine schnellere Alternative?

Update: Durch einige zusätzliche Vorbereitungen (d. H. Vorberechnung einiger hundert Potenzen), wie im Artikel empfohlenhttp://www.ccrwest.org/gordon/fast.pdf Wie in der Antwort von outis weiter unten erwähnt, ist es möglich, eine modulare Exponentiation mit 2048 Bit nur mit höchstens 354 modularen Multiplikationen durchzuführen. (Die herkömmliche Methode zum Quadrieren und Multiplizieren ist viel langsamer: Sie verwendet maximal 4096 modulare Multiplikationen.) Auf diese Weise wird die modulare Exponentiation in Firefox 3.0 um den Faktor 6 und in Google Chrome um den Faktor 4 beschleunigt. Der Grund, warum wir nicht die volle Geschwindigkeit von 4096/354 erreichen, ist, dass der modulare Exponentationsalgorithmus von BigInt bereits schneller als das Quadrat-und-Multiplizieren ist, da er die Montgomery-Reduktion verwendet (http://en.wikipedia.org/wiki/Montgomery_reduction).

Update: Ausgehend von BigInts Code lohnt es sich, zwei handoptimierte (und inline) Karatsuba-Multiplikationsstufen durchzuführen (http://en.wikipedia.org/wiki/Karatsuba_algorithm) und erst dann auf die in BigInt implementierte Base-32768-O (n ^ 2) -Multiplikation zurückgreifen. Dies beschleunigt die Multiplikation für 2048-Bit-Ganzzahlen um den Faktor 2,25. Leider wird der Modulo-Betrieb nicht schneller.

Update: Unter Verwendung der modifizierten Barrett-Reduktion aushttp://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf und Karatsuba - Multiplikations - und Vorberechnungsfähigkeiten (wie inhttp://www.ccrwest.org/gordon/fast.pdf), Kann ich die für eine einzelne Multiplikation benötigte Zeit in Firefox 3.0 von 73 Sekunden auf 12,3 Sekunden senken. Dies scheint das Beste zu sein, was ich tun kann, aber es ist immer noch zu langsam.

Update: Der ActionScript 2 (AS2) -Interpreter im Flash Player ist nicht empfehlenswert, da er langsamer zu sein scheint als der JavaScript-Interpreter in Firefox 3.0: Für Flash Player 9 scheint er 4,2-mal langsamer zu sein, und für Flash Player 10 scheint es 2,35 mal langsamer zu sein. Kennt jemand den Geschwindigkeitsunterschied zwischen ActionScript2 und ActionScript3 (AS3) bei der Nummernvergabe?

Update: Der ActionScript 3 (AS3) -Interpreter in Flash Player 9 ist nicht empfehlenswert, da er ungefähr die gleiche Geschwindigkeit wie JavaScript in Firefox 3.0 aufweist.

Update: Der ActionScript 3 (AS3) -Interpreter in Flash Player 10 kann bis zu 6,5-mal schneller sein als der JavaScript-Interpreter in Firefox 3.0, wennint wird anstelle von verwendetNumber, undVector.<int> wird anstelle von verwendetArray. Zumindest war es 2,41-mal schneller für die 2048-Bit-Ganzzahlmultiplikation. Es könnte sich also lohnen, die modulare Exponentiation in AS3 durchzuführen und sie, falls verfügbar, in Flash Player 10 auszuführen. Bitte beachten Sie, dass dies immer noch langsamer ist als V8, der JavaScript-Interpreter von Google Chrome. Sehenhttp://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html für einen Geschwindigkeitsvergleich verschiedener Programmiersprachen und JavaScript-Implementierungen.

Update: Es gibt eine sehr schnelle Java-Lösung, die über das JavaScript des Browsers aufgerufen werden kann, wenn das Java-Plugin installiert ist. Die folgende Lösung ist ca. 310-mal schneller als die reine JavaScript-Implementierung mit BigInt.

<body>hi0
<script type="text/javascript">
document.body.innerHTML += '<br>hi1';
if ('object'==typeof java) {
  var x = new java.math.BigInteger("123456789123456789", 10);
  var p = new java.math.BigInteger("234567891234567891", 10);
  var g = new java.math.BigInteger("3", 10);
  var v = x.modPow(x, p);
  document.body.innerHTML += '<br>' + v.toString();
  document.body.innerHTML += '<br>' + v.toString(16);
} else {
  document.body.innerHTML += '<br>java plugin not installed';
}
</script></body>

Kann jemand diesen Code in Silverlight (C #) übersetzen?