Mi problema es calcular (g^x) mod p rápidamente en JavaScript, donde ^ es exponenciación, mod es la operación de módulo. Todas las entradas son enteros no negativos, x tiene aproximadamente 256 bits, y p es un número primo de 2048 bits, y g puede tener hasta 2048 bits.exponenciación modular más rápida en JavaScript
La mayor parte del software que he encontrado que puede hacer esto en JavaScript parece usar la biblioteca JavaScript BigInt (http://www.leemon.com/crypto/BigInt.html). Hacer una única exponenciación de dicho tamaño con esta biblioteca lleva unos 9 segundos en mi navegador lento (Firefox 3.0 con SpiderMonkey). Estoy buscando una solución que sea al menos 10 veces más rápida. La idea obvia de usar cuadrado y multiplicar (exponenciación por cuadratura, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) es demasiado lenta para números de 2048 bits: necesita hasta 4096 multiplicaciones.
La actualización del navegador no es una opción. Usar otro lenguaje de programación no es una opción. Enviar los números a un servicio web no es una opción.
¿Existe una alternativa más rápida implementada?
Actualización: Al hacer algunas preparaciones adicionales (es decir, precalculando unos cientos de potencias) como se recomienda en el artículo http://www.ccrwest.org/gordon/fast.pdf mencionado en la respuesta de outis, es posible realizar una exponenciación modular de 2048 bits utilizando solo como máximo 354 multiplicaciones modulares . (El método tradicional de cuadratura y multiplicación es mucho más lento: usa multiplicaciones modulares máximas de 4096). 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 aceleración máxima de 4096/354 es que el algoritmo de exponenciación modular de BigInt ya es más rápido que el cuadrado y el multiplicador, porque usa la reducción de Montgomery (http://en.wikipedia.org/wiki/Montgomery_reduction).
Actualización: A partir del código de BigInt, parece que vale la pena realizar dos niveles de multiplicación de Karatsuba optimizada a mano (y en línea) (http://en.wikipedia.org/wiki/Karatsuba_algorithm), y luego volver a la base 32768 O (n^2) multiplicación implementada en BigInt . Esto acelera las multiplicaciones por un factor de 2.25 para enteros de 2048 bits. Desafortunadamente, la operación del módulo no se vuelve más rápida.
Actualización: El uso de la reducción Barrett modificado definido en http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf y multiplicación Karatsuba y precomputen poderes (como se define en http://www.ccrwest.org/gordon/fast.pdf), puedo bajar el tiempo necesario para una sola multiplicación de 73 segundos a 12,3 segundos en Firefox 3.0. Esto parece ser lo mejor que puedo hacer, pero todavía es demasiado lento.
Actualización: no vale la pena usar el intérprete de ActionScript 2 (AS2) en Flash Player, porque 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 chrunching numérico?
Actualización: El intérprete de ActionScript 3 (AS3) en Flash Player 9 no vale la pena usarlo porque tiene casi la misma velocidad que el JavaScript int Firefox 3.0.
Actualización: El intérprete de ActionScript 3 (AS3) en Flash Player 10 puede ser hasta 6,5 veces más rápido que el intérprete de JavaScript en Firefox 3.0 si se utiliza en lugar de intNumber y Vector.<int> se utiliza en lugar de Array. Al menos fue 2.41 veces más rápido para la multiplicación de enteros grandes de 2048 bits. Por lo tanto, valdría la pena realizar la exponenciación modular en AS3, ejecutándola en Flash Player 10 si está disponible. Tenga en cuenta que esto es aún más lento que 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 e implementaciones de JavaScript.
Actualización: existe una solución Java muy rápida, que puede invocarse desde el JavaScript del navegador si está instalado el complemento de Java. La siguiente solución es aproximadamente 310 veces más rápida que la implementación de JavaScript puro con 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 a Silverlight (C#)?
Tengo que confirmar que BigInt está bastante bien optimizado. Intenté implementar la multiplicación usando el algoritmo Karatsuba, pero se volvió 4 veces más lento que la multiplicación simple O (n^2) de BigInt. – pts
Gracias por mencionar el artículo, parece prometedor. – pts
Usando BigInt.js con las técnicas del artículo que ha vinculado podría acelerar la multiplicación modular de enteros de 2048 bits por un factor de 6 en Firefox 3.0 y un factor de 4 en Google Chrome. Desafortunadamente, esto todavía es demasiado lento para mí, así que tengo que encontrar un protocolo de criptografía diferente, que necesita menos cálculos. – pts