Más rápido exponenciación modular en JavaScript

Question

Mi problema es calcular (g^x) mod p rápidamente en JavaScript, donde ^ es la exponenciación, mod es el módulo de la operación.Todas las entradas son números enteros no negativos, x tiene alrededor de 256 bits, y p es un número primo de 2048 bits, y g puede disponer de hasta 2048 bits.

La mayoría de los programas que me he encontrado con que puede hacerlo en JavaScript parece utilizar el JavaScript de tipo BigInt (biblioteca dehttp://www.leemon.com/crypto/BigInt.html).Haciendo una sola exponenciación de tal tamaño con esta biblioteca tiene unos 9 segundos en mi lento el navegador (Firefox 3.0 con mono araña).Estoy buscando una solución que es al menos 10 veces más rápido.La idea obvia de usar cuadrado y multiplicar (exponenciación al cuadrado, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) es demasiado lento para 2048 bits de los números:se necesita un máximo de 4096 multiplicaciones.

Actualizar el navegador no es una opción.El uso de otro lenguaje de programación no es una opción.El envío de los números a un servicio web no es una opción.

Hay una alternativa más rápida implementado?

Actualización:Haciendo algo de extra preparados (es decir,precomputing de unos pocos cientos de poderes) según lo recomendado por el artículo http://www.ccrwest.org/gordon/fast.pdf se menciona en outis respuesta a continuación, es posible hacer a un 2048 bits exponenciación modular utilizando sólo en la mayoría de los 354 modular multiplicaciones.(El tradicional cuadrado y multiplicar método es mucho más lento:utiliza el máximo de 4096 modular multiplicaciones.) Hacerlo acelera la exponenciación modular por un factor de 6 en Firefox 3.0, y por un factor de 4 en Google Chrome.La razón por la que no estamos obteniendo la plena aceleración de 4096/354 es que BigInt modular de exponentation algoritmo ya es más rápido que el cuadrado y se multiplica, porque se utiliza la reducción de Montgomery (http://en.wikipedia.org/wiki/Montgomery_reduction).

Actualización:A partir de BigInt del código, parece que merece la pena hacer dos niveles de mano-optimizado (y en línea) Karatsuba multiplicación (http://en.wikipedia.org/wiki/Karatsuba_algorithm), y sólo entonces volver a la base-32768 O(n^2) multiplicación implementado en BigInt.Esto acelera la multiplicación por un factor de 2.25 para 2048 bits enteros.Por desgracia, el modulo de la operación no sea más rápido.

Actualización:Mediante la modificación de Barrett reducción se define en http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf y Karatsuba multiplicación y precomputing poderes (como se define en http://www.ccrwest.org/gordon/fast.pdf), Puedo obtener el tiempo necesario para una sola multiplicación de 73 segundos 12,3 segundos en Firefox 3.0.Este parece ser el mejor que puedo hacer, pero todavía es demasiado lento.

Actualización:El ActionScript 2 (AS2) intérprete en el Flash Player no es digno de usar, ya que parece ser más lento que el intérprete de JavaScript en Firefox 3.0:para Flash Player 9, parece ser 4.2 veces más lento, y para Flash Player 10, parece ser 2.35 veces más lento.¿Alguien sabe la diferencia de velocidad entre ActionScript2 y ActionScript3 (AS3) para el número de chrunching?

Actualización:El ActionScript 3 (AS3) intérprete en Flash Player 9 que no vale la pena usar porque tiene casi la misma velocidad que el JavaScript int Firefox 3.0.

Actualización:El ActionScript 3 (AS3) intérprete de Flash Player 10 puede ser de hasta 6,5 veces más rápido que el intérprete de JavaScript en Firefox 3.0 si int se utiliza en lugar de Number, y Vector.<int> se utiliza en lugar de Array.Al menos era 2.41 veces más rápido de 2048 bits gran multiplicación de enteros.Por lo que podría ser vale la pena hacer la exponenciación modular en AS3, la ejecución de Flash Player 10, si está disponible.Por favor, tenga en cuenta que esto es aún más lento que el V8, el intérprete de JavaScript de Google Chrome.Ver http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html para una comparación de velocidad de varios lenguajes de programación y las implementaciones de JavaScript.

Actualización:Hay una muy rápida solución de Java, que se puede llamar desde el navegador JavaScript si el plugin de Java está instalado.La siguiente solución es de alrededor de 310 veces más rápido que el puro JavaScript utilizando la implementación 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>

¿Alguien puede traducir este código de Silverlight (C#)?

Answer 1

Habría alguna otra tecnología del lado del cliente que se puede llamar desde JS, tales como un applet de Java o Flash de la película, ser aceptable?BigInt del enfoque ya es bastante rápido.Usted puede ajustar BigInt, o usted puede tratar de un algoritmo diferente, pero usted probablemente no va a obtener un orden de magnitud de la mejora.

Answer 2

Yo uso "%" para modular (mod) y "/" para la división de enteros.Deje que la función f(p,g,x,r) calcular (r*g^x)%p con la condición de que rf() puede ser implementado como:

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
}

Esta rutina consiste en un poco más de cálculo, sino que cada entero es menos de 4096 bits, lo que es generalmente mucho menor que g^x.Creo que esto podría ser más eficiente que el cálculo directo.También tenga en cuenta que g^(x%i) se puede calcular de una manera más rápida debido a que hemos calculado g^(i+1).

EDITAR:ver este post.Mehrdad da el derecho (y mejor) solución.

Answer 3

¿Por qué no hacerlo de lado de servidor en algún tipo de servicio web utilizando la más apropiada, en un lenguaje como C?Los tiempos de entonces será tiempo para un viaje ida y vuelta (a menos de 9 segundos), además de la hora del servidor para calcular el resultado con el uso de algunos BigInt biblioteca en código nativo.Esto es probable que sea mucho más rápido.

Answer 4

Pruebe este Montgomery modular de reducción de http://code.google.com/p/bi2php/ en JavaScript.

Answer 5

Me encantaría ver el código fuente modificado BigInt la biblioteca está disponible en cualquier lugar?