JavaScriptでの最速の累乗累乗

Question

私の問題は、^が累乗で、modがモジュロ演算である場合、JavaScriptですぐに(g^x) mod pを計算することです。すべての入力は非負整数で、xは約256ビット、は2048ビットの素数で、gは2048ビットまでです。

JavaScriptでこれを行うことができるソフトウェアのほとんどはJavaScript BigIntライブラリ（http://www.leemon.com/crypto/BigInt.html）を使用しているようです。このライブラリでこのようなサイズの累乗を1回行うのは、遅いブラウザ（Firefox 3.0とSpiderMonkey）で約9秒かかります。私は少なくとも10倍速いソリューションを探しています。平方乗算（二乗法による累乗、http://en.wikipedia.org/wiki/Exponentiation_by_squaring）を使用するという明白な考え方は、2048ビットの数値に対しては遅すぎます。最大4096回の乗算が必要です。

ブラウザのアップグレードはオプションではありません。別のプログラミング言語を使用することは選択肢ではありません。数字をWebサービスに送信することは選択肢ではありません。

もっと速い代替手段が実装されていますか？

更新：下記の記事「回答」に記載されている記事http://www.ccrwest.org/gordon/fast.pdfで推奨されているように、いくつかの余分な準備（すなわち、数百の事前計算）を行うことによって、最大354回のモジュラ乗算を使用する2048ビットのべき乗剰余演算。 （従来の二乗乗算法ははるかに遅く、最大4096の乗算を使用します）。これにより、モジュール式べき乗はFirefox 3.0では6倍、Google Chromeでは4倍に高速化されました。私たちが4096/354の完全なスピードアップを得られないのは、BigIntのモジュラ指数アルゴリズムが、モンゴメリ削減（http://en.wikipedia.org/wiki/Montgomery_reduction）を使用しているので、すでに二乗乗算より高速です。

更新：BigIntのコードから、2つのレベルの手最適化された（そしてインライン化された）Karatsuba乗算（http://en.wikipedia.org/wiki/Karatsuba_algorithm）を実行し、BigIntで実装された32768のO（n^2） 。これにより、2048ビットの整数の乗算が2.25倍に高速化されます。残念ながら、モジュロ演算は高速化されません。

更新：http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdfで定義された修正されたバレット削減と、Karatsuba乗算と事前計算能力（http://www.ccrwest.org/gordon/fast.pdfで定義）を使用すると、Firefox 3.0で73秒から12.3秒までの1回の乗算に必要な時間を短縮できます。これは私ができる最高のようですが、まだ遅すぎます。

アップデート：Flash PlayerのActionScript 2（AS2）インタプリタは、Firefox 3.0のJavaScriptインタプリタよりも遅いため、使用価値はありません。Flash Player 9では4.2倍遅くなり、 Flash Player 10の場合、2.35倍遅くなっているようです。誰かが、数値の変化に合わせてActionScript2とActionScript3（AS3）の速度の違いを知っていますか？

更新：Flash Player 9のActionScript 3（AS3）インタプリタは、JavaScript int Firefox 3.0とほぼ同じ速度を持つため、使用する価値はありません。

更新：intはNumberの代わりに使用され、そしてVector.<int>代わりにArrayの使用されている場合のFlash Player 10でのActionScript 3（AS3）インタプリタは、Firefox 3.0で最大6.5倍高速JavaScriptインタープリタよりもすることができます。少なくとも2048ビットの大整数乗算では2.41倍高速でした。したがって、AS3でのべき乗剰余演算を行う価値があるかもしれません。可能であれば、Flash Player 10で実行します。これはまだGoogle ChromeのJavaScriptインタープリタであるV8よりも遅いことに注意してください。さまざまなプログラミング言語とJavaScript実装の速度比較については、http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.htmlを参照してください。

更新：非常に高速なJavaソリューションがあります。これは、Javaプラグインがインストールされている場合、ブラウザのJavaScriptから呼び出すことができます。次のソリューションは、BigIntを使用する純粋なJavaScript実装より約310倍高速です。

誰でもこのコードをSilverlight（C＃）に翻訳できますか？

Answer 1

JavaアプレットやFlashムービーなど、JSから呼び出し可能な他のクライアント側の技術は受け入れられますか？ BigIntのapproachはすでにかなり速いです。 BigIntを微調整するか、different algorithmを試すことができますが、おそらく大した改善はありません。

Answer 2

Cのようなより適切な言語を使用して、何らかの種類のWebサービスでサーバー側を使ってみませんか？時間は、1ラウンドトリップ（9秒未満）の時間と、サーバがネイティブコードでいくつかのBigIntライブラリを使用して結果を計算する時間です。これははるかに高速になる可能性があります。

Answer 3

私はモジュラー（mod）に "％"を使用し、整数除算には "/"を使用します。 r < pとg < pの条件で関数f（p、g、x、r）が（r * g^x）％pを計算するとします。 fは（）として実装することができる。

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 
} 

このルーチンは、もう少し計算を必要とするが、各整数は、通常G^xよりもはるかに小さい未満4096ビットです。私はこれが直接計算よりも効率的であると信じています。また、g ^（i + 1）を計算したので、g ^（x％i）はより高速に計算できることにも注意してください。

編集：this postを参照してください。 Mehrdadは正しい（そしてより良い）ソリューションを提供します。

Answer 4

JavaScriptでhttp://code.google.com/p/bi2php/からこのモンゴメリモジュラを試してみてください。

Answer 5

変更されたBigIntライブラリのソースコードはどこからでも入手できますか？