Plus rapide exponentiation modulaire en JavaScript

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

Question

Mon problème est de calculer rapidement (g^x) mod p en JavaScript, où ^ est exponentiation, mod est l'opération modulo. Toutes les entrées sont des nombres entiers non négatifs, x a environ 256 bits et p est un nombre premier de 2048 bits, et g peut avoir jusqu'à 2048 bits.

La plupart des logiciels que j'ai trouvé qui peut le faire en JavaScript semble utiliser la bibliothèque JavaScript BigInt ( http://en.wikipedia.org/ wiki / Exponentiation_by_squaring ) est trop lent pour les numéros 2048 bits. il a besoin jusqu'à 4096 multiplications

Mise à niveau du navigateur n'est pas une option. En utilisant un autre langage de programmation ne sont pas une option. L'envoi des numéros à un service Web est pas une option.

Y at-il mis en œuvre une alternative plus rapide?

Mise à jour: En faisant quelques préparations supplémentaires (c.-à-précalcul quelques centaines de pouvoirs) tel que recommandé par l'article http://www.ccrwest.org/gordon/fast.pdf mentionné dans outis' réponse ci-dessous, il est possible de faire une exponentiation modulaire 2048 bits en utilisant seulement au plus 354 multiplications modulaires. (La méthode traditionnelle carré et multiplication est beaucoup plus lente: il utilise au maximum 4096 multiplications modulaires.) Faire des vitesses si l'exponentiation modulaire par un facteur de 6 à Firefox 3.0, et par un facteur de quatre dans Google Chrome. La raison pour laquelle nous ne recevons pas le plein de 4096/354 est speedup cet algorithme de exponentation modulaire BigInt est déjà plus rapide que carré et se multiplient, car il utilise la réduction Montgomery ( http://en.wikipedia.org/wiki/Montgomery_reduction ).

Mise à jour: A partir de code de BigInt, il semble utile de faire deux niveaux d'optimisation à la main (et inline) multiplication Karatsuba ( http: //www.lirmm .fr / arith18 / papiers / hasenplaugh-FastModularReduction.pdf et la multiplication Karatsuba et les pouvoirs précalcul (tel que défini dans http://www.ccrwest.org/gordon/fast.pdf ), je peux descendre le temps nécessaire pour une seule multiplication de 73 secondes à 12,3 secondes dans Firefox 3.0. Cela semble être le meilleur que je peux le faire, mais il est encore trop lent.

Mise à jour: Le code ActionScript 2 (AS2) interprète dans le Flash Player ne vaut pas l'utiliser, car il semble être plus lent que l'interpréteur JavaScript dans Firefox 3.0: pour Flash Player 9, il semble être 4,2 fois plus lent, et pour flash player 10, il semble être 2,35 fois plus lent. Quelqu'un sait-il la différence de vitesse entre ActionScript2 et ActionScript3 (AS3) pour le numéro chrunching?

Mise à jour: L'interpréteur ActionScript 3 (AS3) dans Flash Player 9 n'est pas la peine d'utiliser, car il a à peu près la même vitesse que l'int Firefox 3.0 JavaScript

.

Mise à jour: L'interpréteur ActionScript 3 (AS3) dans Flash Player 10 peut être up à 6,5 fois plus rapide que l'interpréteur JavaScript dans Firefox 3.0 si int est utilisé au lieu de Number et Vector.<int> est utilisé au lieu de Array. Au moins, il était 2,41 fois plus rapide pour la multiplication grand nombre entier 2048 bits. Il pourrait donc être utile de faire l'exponentiation modulaire AS3, exécution dans Flash Player 10 si elle est disponible. S'il vous plaît noter que ceci est encore plus lent que V8, l'interpréteur JavaScript de Google Chrome. Voir http://ptspts.blogspot.com/2009/10/ javascript-et-actionscript performance.html pour une comparaison de vitesse de différents langages de programmation et de mise en oeuvre JavaScript.

Mise à jour: Il y a une solution Java très rapide, qui peut être appelé à partir de JavaScript du navigateur si le plug-in Java est installé. La solution suivante est d'environ 310 fois plus rapide que la mise en œuvre pur JavaScript à l'aide 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>

Quelqu'un peut-il traduire ce code Silverlight (C #)?

Était-ce utile?

La solution

Est-ce que d'une autre technologie côté client qui est appelable de JS, comme une applet Java ou un film Flash, acceptable? est déjà assez rapide. Vous pouvez modifier BigInt, ou vous pouvez essayer un différent algorithme, mais vous avez probablement gagné » t obtenir un ordre d'amélioration de la grandeur.

Autres conseils

J'utilise "%" pour modulaire (mod) et "/" pour la division entière. Soit la fonction f (p, g, x, r) calculer (r * g ^ x)% p à la condition que 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
}

Cette routine implique un peu plus de calcul, mais chaque nombre entier est inférieur à 4096 bits qui est généralement beaucoup plus faible que g ^ x. Je crois que cela pourrait être plus efficace que le calcul direct. Notez également que g ^ (x% i) peut être calculé d'une manière plus rapide parce que nous avons calculé g ^ (i + 1).

EDIT: voir ce message . Mehrdad donne la bonne solution (et mieux).

Pourquoi ne pas le faire côté serveur dans une sorte de service Web en utilisant un langage plus approprié comme C? Les temps sera alors temps pour un aller-retour (moins de 9 secondes), plus le temps pour le serveur pour calculer le résultat en utilisant une bibliothèque BigInt dans le code natif. Ceci est susceptible d'être beaucoup plus rapide.

Essayez cette réduction modulaire de Montgomery de http://code.google.com/p/bi2php/ JavaScript.

J'aimerais voir le code source à votre bibliothèque BigInt modifiée - est-il disponible partout

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top