Mais rápido exponenciação modular em JavaScript

Question

O meu problema é calcular (g^x) mod p rapidamente em JavaScript, onde ^ é exponenciação, mod é a operação de módulo. Todas as entradas são inteiros não negativos, x tem cerca de 256 bits, e p é um número primo de 2048 bits, e g pode ter até 2048 bits.

A maioria dos softwares que eu encontrei que pode fazer isso em JavaScript parece usar a biblioteca JavaScript BigInt ( http://www.leemon.com/crypto/BigInt.html ). Fazendo uma única exponenciação de tal dimensão, com esta biblioteca leva cerca de 9 segundos em meu navegador lento (Firefox 3.0 com SpiderMonkey). Eu estou procurando uma solução que é pelo menos 10 vezes mais rápido. A ideia óbvia de usar quadrados e-multiplicar (exponenciação por quadratura, http://en.wikipedia.org/ wiki / Exponentiation_by_squaring ) é muito lento para os números de 2048 bits: ele precisa até 4096 multiplicações

.

A atualização do navegador não é uma opção. Usando outra linguagem de programação não é uma opção. Enviando os números para um serviço web não é uma opção.

Existe uma alternativa mais rápida implementado?

Update: Ao fazer algumas preparações extras (ie precomputing algumas centenas de poderes) como recomendado pelo artigo http://www.ccrwest.org/gordon/fast.pdf mencionado no outis' resposta abaixo, é possível fazer a uma exponenciação modular de 2048 bits usando apenas, no máximo, 354 multiplicações modulares. (O método square-and-multiplicam tradicional é muito mais lento: ele usa máximas 4096 multiplicações modulares.) Fazer isso acelera a exponenciação modular por um fator de 6 em Firefox 3.0, e por um fator de 4 em Google Chrome. A razão pela qual não estamos recebendo a aceleração cheio de 4096/354 é que o algoritmo exponentation modular de BigInt já mais rápido do que quadrado-and-multiplicam é, porque ele usa redução Montgomery ( http://en.wikipedia.org/wiki/Montgomery_reduction ).

Update: A partir do código do BigInt, parece que vale a pena fazer dois níveis de (e inline) otimizado mão Karatsuba multiplicação ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ), e só então reverter para a base 32768-o (n ^ 2) multiplicação implementado em BigInt. Isso acelera multiplicações por um fator de 2,25 para números inteiros de 2048 bits. Infelizmente, a operação de módulo não se torne mais rápida.

Update: Usando a redução Barrett modificado definido na http: //www.lirmm .fr / arith18 / papers / hasenplaugh-FastModularReduction.pdf e Karatsuba multiplicação e precomputing poderes (como definido na http://www.ccrwest.org/gordon/fast.pdf ), eu posso descer o tempo necessário para uma única multiplicação de 73 segundos para 12,3 segundos no Firefox 3.0. Este parece ser o melhor que posso fazer, mas ainda é muito lento.

Update: A 2 (AS2) interpretador ActionScript no Flash Player não vale a pena usar, porque ele parece ser mais lento do que o interpretador de JavaScript no Firefox 3.0: para o Flash Player 9, parece ser 4,2 vezes mais lento, e para o flash player 10, parece ser 2,35 vezes mais lento. Alguém sabe a diferença de velocidade entre ActionScript2 e ActionScript3 (AS3) para o número chrunching?

Update:. O intérprete ActionScript 3 (AS3) no Flash Player 9 não vale a pena usar porque tem praticamente a mesma velocidade que o JavaScript int Firefox 3.0

Update: O intérprete ActionScript 3 (AS3) no Flash Player 10 pode ser up a 6,5 ??vezes mais rápido do que o interpretador JavaScript em Fogo 3,0 int se é usado em vez de Number, e Vector.<int> é usado em vez de Array. Pelo menos era 2,41 vezes mais rápido para 2048 bit multiplicação inteiro grande. Assim, pode ser vale a pena fazer a exponenciação modular em AS3, executá-lo no Flash Player 10, se disponível. Por favor note que este é ainda mais lento do que V8, o interpretador JavaScript do Google Chrome é. Consulte http://ptspts.blogspot.com/2009/10/ javascript-and-actionscript-performance.html para uma comparação de velocidade de várias linguagens de programação e implementações de JavaScript.

Update: Há uma solução Java muito rápido, o que pode ser chamado de JavaScript do navegador se o plugin Java está instalado. A solução a seguir é de cerca de 310 vezes mais rápido do que a implementação JavaScript puro utilizando 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>

Alguém pode traduzir este código para Silverlight (C #)?

Answer 1

Será que alguma outra tecnologia do lado do cliente que é que pode ser chamado de JS, como um applet Java ou filme Flash, ser aceitável? já é bastante rápido. Você pode ajustar BigInt, ou você pode tentar um diferente algoritmo , mas você provavelmente ganhou' t obter uma ordem de melhoria magnitude.

Answer 2

Eu uso "%" para modular (mod) e "/" para divisão inteira. Deixe que a função f (P, G, X, R) calcular (r * g ^ x)% p com a condição de 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
}

Esta rotina envolve um pouco mais de cálculo, mas cada inteiro é menor que 4096 bits que é geralmente muito menor do que g ^ x. Eu acredito que este poderia ser mais eficiente do que o cálculo direto. De referir ainda que g ^ (x% i) pode ser calculada de uma forma mais rápida porque, calculou-g ^ (i + 1).

EDIT: consulte este post . Mehrdad dá o direito (e melhor) solução.

Answer 3

Por que não fazê-lo do lado do servidor em algum tipo de serviço da web usando uma linguagem mais apropriada como C? Vezes será então tempo para uma ida e volta (menos de 9 segundos), mais o tempo para o servidor para calcular o resultado usando alguma biblioteca BigInt em código nativo. Esta é susceptível de ser muito mais rápido.

Answer 4

Tente esta redução modular Montgomery de http://code.google.com/p/bi2php/ em JavaScript.

Answer 5

Eu adoraria ver o código fonte para a biblioteca BigInt modificado -? É disponível em qualquer lugar