Esponenziazione modulare più veloce in JavaScript

Question

Il mio problema è calcolare (g^x) mod p rapidamente in JavaScript, dove ^ è l'elevamento a potenza, mod è l'operazione modulo.Tutti gli input sono numeri interi non negativi, x ha circa 256 bit e p è un numero primo di 2048 bit e g può avere fino a 2048 bit.

La maggior parte del software che ho trovato in grado di eseguire questa operazione in JavaScript sembra utilizzare la libreria JavaScript BigInt (http://www.leemon.com/crypto/BigInt.html).Fare una singola esponenziazione di tali dimensioni con questa libreria richiede circa 9 secondi sul mio browser lento (Firefox 3.0 con SpiderMonkey).Sto cercando una soluzione che sia almeno 10 volte più veloce.L'idea ovvia di usare il quadrato e la moltiplicazione (elevamento a potenza mediante quadrato, http://en.wikipedia.org/wiki/Exponentiation_by_squareing) è troppo lento per i numeri a 2048 bit:necessita fino a 4096 moltiplicazioni.

L'aggiornamento del browser non è un'opzione.L'utilizzo di un altro linguaggio di programmazione non è un'opzione.L'invio dei numeri a un servizio web non è un'opzione.

È stata implementata un'alternativa più rapida?

Aggiornamento:Eseguendo alcuni preparativi aggiuntivi (ad es.precalcolando alcune centinaia di potenze) come raccomandato dall'articolo http://www.ccrwest.org/gordon/fast.pdf menzionato nella risposta di Outis di seguito, è possibile eseguire un'esponenziazione modulare a 2048 bit utilizzando solo al massimo 354 moltiplicazioni modulari.(Il metodo tradizionale del quadrato e della moltiplicazione è molto più lento:utilizza un massimo di 4096 moltiplicazioni modulari.) In questo modo si accelera l'esponenziazione modulare di un fattore 6 in Firefox 3.0 e di un fattore 4 in Google Chrome.Il motivo per cui non otteniamo la piena velocità di 4096/354 è che l'algoritmo di esponenza modulare di BigInt è già più veloce di eleva e moltiplica, perché utilizza la riduzione di Montgomery (http://en.wikipedia.org/wiki/Montgomery_reduction).

Aggiornamento:Partendo dal codice di BigInt, sembra utile eseguire due livelli di moltiplicazione di Karatsuba ottimizzati manualmente (e incorporati) (http://en.wikipedia.org/wiki/Karatsuba_algorithm), e solo allora tornare alla moltiplicazione O(n^2) in base 32768 implementata in BigInt.Ciò accelera le moltiplicazioni di un fattore di 2,25 per gli interi a 2048 bit.Sfortunatamente, l'operazione modulo non diventa più veloce.

Aggiornamento:Utilizzando la riduzione di Barrett modificata definita in http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf e i poteri di moltiplicazione e precalcolo di Karatsuba (come definiti in http://www.ccrwest.org/gordon/fast.pdf), posso ridurre il tempo necessario per una singola moltiplicazione da 73 secondi a 12,3 secondi in Firefox 3.0.Questo sembra essere il meglio che posso fare, ma è ancora troppo lento.

Aggiornamento:Non vale la pena utilizzare l'interprete ActionScript 2 (AS2) in Flash Player, perché sembra essere più lento dell'interprete JavaScript in Firefox 3.0:per Flash Player 9 sembra essere 4,2 volte più lento e per Flash Player 10 sembra essere 2,35 volte più lento.Qualcuno conosce la differenza di velocità tra ActionScript2 e ActionScript3 (AS3) per la riduzione dei numeri?

Aggiornamento:Non vale la pena utilizzare l'interprete ActionScript 3 (AS3) in Flash Player 9 perché ha quasi la stessa velocità di JavaScript int Firefox 3.0.

Aggiornamento:L'interprete ActionScript 3 (AS3) in Flash Player 10 può essere fino a 6,5 ​​volte più veloce dell'interprete JavaScript in Firefox 3.0 se int viene utilizzato al posto di Number, E Vector.<int> viene utilizzato al posto di Array.Almeno era 2,41 volte più veloce per la moltiplicazione di numeri interi di grandi dimensioni a 2048 bit.Quindi potrebbe valere la pena eseguire l'elevamento a potenza modulare in AS3, eseguindolo in Flash Player 10, se disponibile.Tieni presente che questo è ancora più lento di V8, l'interprete JavaScript di Google Chrome.Vedere http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html per un confronto veloce tra vari linguaggi di programmazione e implementazioni JavaScript.

Aggiornamento:Esiste una soluzione Java molto veloce, che può essere richiamata dal JavaScript del browser se è installato il plugin Java.La seguente soluzione è circa 310 volte più veloce della pura implementazione JavaScript utilizzando 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>

Qualcuno può tradurre questo codice in Silverlight (C#)?

Answer 1

Sarebbe accettabile qualche altra tecnologia lato client richiamabile da JS, come un'applet Java o un filmato Flash?BigInt approccio è già abbastanza veloce.Puoi modificare BigInt oppure puoi provare a algoritmo diverso, ma probabilmente non otterrai un miglioramento di un ordine di grandezza.

Answer 2

Utilizzo "%" per modulare (mod) e "/" per divisione intera.Sia la funzione f(p,g,x,r) a calcolare (r*g^x)%p a condizione che r<p e g<p.f() può essere implementato come:

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
}

Questa routine richiede un po' più di calcoli, ma ogni intero è inferiore a 4096 bit, che di solito è molto più piccolo di g^x.Credo che questo potrebbe essere più efficiente del calcolo diretto.Si noti inoltre che g^(x%i) può essere calcolato in modo più veloce perché abbiamo calcolato g^(i+1).

MODIFICARE:Vedere questo post.Mehrdad fornisce la soluzione giusta (e migliore).

Answer 3

Perché non farlo lato server in una sorta di servizio Web utilizzando un linguaggio più appropriato come C?I tempi saranno quindi il tempo per un viaggio di andata e ritorno (meno di 9 secondi), più il tempo impiegato dal server per calcolare il risultato utilizzando una libreria BigInt nel codice nativo.È probabile che ciò avvenga molto più velocemente.

Answer 4

Prova questa riduzione modulare Montgomery da http://code.google.com/p/bi2php/ su JavaScript.

Answer 5

Mi piacerebbe vedere il codice sorgente della tua libreria BigInt modificata: è disponibile ovunque?