Schnellste modulare Potenzierung in JavaScript

StackOverflow https://stackoverflow.com/questions/1450608

Frage

Mein Problem (g^x) mod p schnell in JavaScript zu berechnen ist, wo ^ Potenzierung ist, mod ist die Modulo-Operation. Alle Eingänge sind positive ganze Zahlen, x hat etwa 256 Bits und p eine Primzahl von 2048 Bits und g können bis zu 2048 Bit haben.

Die meisten der Software, die ich gefunden habe, dass dies in JavaScript tun können, scheint die JavaScript BigInt Bibliothek zu verwenden ( http://en.wikipedia.org/ wiki / Exponentiation_by_squaring ) für 2048-Bit-Zahlen zu langsam ist. es bis 4096 Multiplikationen braucht bis

Sie den Browser Upgrade ist keine Option. eine andere Programmiersprache ist keine Option. Senden Sie die Zahlen auf einen Web-Service ist keine Option.

Gibt es eine schnellere Alternative umgesetzt?

Update: Durch zusätzliche Vorbereitungen zu tun (dh precomputing ein paar hundert Kräfte), wie durch den Artikel empfohlen mit nur höchstens 354 modularen Multiplikationen http://www.ccrwest.org/gordon/fast.pdf erwähnte in Outis' unten beantworten, ist es möglich, auf eine 2048-Bit modulare Potenzierung zu tun. (Die traditionelle Square-and-Multiply-Methode ist viel langsamer: es maximal 4096 modulare Multiplikationen verwendet.) Doing so beschleunigt die modulare Potenzierung um den Faktor 6 in Firefox bis 3,0, und um einen Faktor von 4 in Google Chrome. Der Grund, warum wir nicht die volle Beschleunigung von 4096/354 bekommen ist, dass BigInt modulare exponentation Algorithmus ist bereits schneller als quadratisch-and-Multiply, weil es Montgomery-Reduktion verwendet ( http://en.wikipedia.org/wiki/Montgomery_reduction ).

Update: Ab BigInt Code, scheint es sinnvoll zu tun zwei Ebenen von Hand optimiert (und inlined) Karatsuba-Multiplikation ( http: //www.lirmm .fr / arith18 / paper / hasenplaugh-FastModularReduction.pdf und Karatsuba-Multiplikation und precomputing Kräfte (wie in http://www.ccrwest.org/gordon/fast.pdf ), kann ich die Zeit für eine einzige Multiplikation von 73 Sekunden bis 12,3 Sekunden in Firefox 3.0 erforderlich runter. Dies scheint zu sein, das Beste, was ich tun kann, aber es ist immer noch zu langsam.

Update: Das Actionscript 2 (AS2) Interpreter im Flash Player ist nicht wert, zu verwenden, da es langsamer als die JavaScript-Interpreter in Firefox zu sein scheint 3.0: Flash Player 9, scheint es 4,2 mal langsamer zu sein, und für Flash Player 10, so scheint es 2,35 mal langsamer zu sein. Weiß jemand, die Geschwindigkeitsdifferenz zwischen ActionScript2 und ActionScript3 (AS3) für Nummer chrunching?

Update: Die Actionscript 3 (AS3) Interpreter in Flash Player 9 ist nicht lohnt sich der Einsatz, weil es nur etwa die gleiche Geschwindigkeit wie die JavaScript int Firefox 3.0 hat

.

Update: Die Actionscript 3 (AS3) Interpreter in Flash Player 10 u kann seinp zu 6,5-mal schneller als die JavaScript-Interpreter in Firefox 3.0, wenn int statt Number verwendet, und Vector.<int> statt Array verwendet. Zumindest war es 2,41-mal schneller für 2048 Bit große Integer-Multiplikation. So könnte es tun, die modulare Potenzierung in AS3 wert sein, es in Flash Player 10, wenn vorhanden Ausführung. Bitte beachten Sie, dass dies immer noch langsamer als V8, die JavaScript-Interpreter von Google Chrome. Siehe http://ptspts.blogspot.com/2009/10/ Javascript-and-Actionscript-performance.html für einen Geschwindigkeitsvergleich verschiedenen Programmiersprachen und JavaScript-Implementierungen.

Update: Es ist eine sehr schnelle Java-Lösung, die vom Browser des JavaScript aufgerufen werden kann, wenn die Java-Plugin installiert ist. Die folgende Lösung ist etwa 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, um Silverlight (C #) übersetzen?

War es hilfreich?

Lösung

Würde eine andere Client-Seite-Technologie, die von JS, wie ein Java-Applet oder Flash-Film aufrufbar ist, akzeptabel? BigInt Ansatz ist schon ziemlich schnell. Sie können BigInt zwicken, oder Sie können eine anderen Algorithmus rel="nofollow, aber wahrscheinlich gewonnen‘ erhalten t eine Größenordnung verbessert werden.

Andere Tipps

I "%" für modular (mod) und "/" für ganzzahlige Division verwenden. Lassen Funktion f (p, g, x, r) Berechnen (r * g ^ x)% p die Bedingung, daß r 

bigint_t f(p,g,x,r) {
  bigint_t i, z = g, y;
  for (i = 1; i < x; ++i) {
    y = z; z *= g;
    if (z > p) break;
  }
  if (i >= x - 1) return r*z%p; // g^x*r%p = g^x*r
  else return f(p,y,x/i,g^(x%i)*r%p); // reduce to (r*g^(x%i)%p)*(g^i)^(x/i)%p
}

Diese Routine beinhaltet ein wenig mehr Berechnung, aber jede ganze Zahl kleiner als 4096 Bits, die in der Regel viel kleiner als g ^ x. Ich glaube, dies ist als die direkte Berechnung effizienter sein könnte. Beachten Sie auch, dass g ^ (x% i) in einer schnelleren Art und Weise berechnet werden, da wir berechnet haben g ^ (i + 1).

EDIT: siehe diesen Beitrag . Mehrdad gibt das Recht (und bessere) Lösung.

Warum tun Sie es nicht Server-Seite in irgendeiner Art von Web-Service eine angemessenere Sprache wie C verwenden? Die Zeiten werden dann Zeit für eine Hin- und Rückfahrt (weniger als 9 Sekunden), zuzüglich der Zeit für den Server das Ergebnis mit einigen BigInt Bibliothek in nativen Code zu berechnen. Dies ist wahrscheinlich viel schneller sein.

Versuchen Sie, diese modulare Montgomery-Reduktion von http://code.google.com/p/bi2php/ auf JavaScript.

Ich würde gerne den Quellcode Ihrer modifizierten BigInt Bibliothek zu sehen - es ist überall verfügbar

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top