JavaScript での最速のべき乗剰余演算

StackOverflow https://stackoverflow.com/questions/1450608

質問

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

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

ブラウザをアップグレードすることはできません。別のプログラミング言語を使用することはできません。番号を Web サービスに送信することはできません。

より高速な代替手段は実装されていますか?

アップデート：追加の準備を行うことによって (例:記事で推奨されているように、数百乗を事前計算します） http://www.ccrwest.org/gordon/fast.pdf 以下の outis の回答で述べられているように、最大​​ 354 個の剰余乗算のみを使用して 2048 ビットのべき乗剰余演算を実行することが可能です。(従来の 2 乗して乗算する方法ははるかに時間がかかります。これにより、べき乗剰余演算が Firefox 3.0 では 6 倍、Google Chrome では 4 倍高速化されます。4096/354 の完全な高速化が得られない理由は、BigInt のべき乗剰余アルゴリズムがモンゴメリ リダクションを使用しているため、すでに 2 乗乗算よりも高速であるためです (http://en.wikipedia.org/wiki/Montgomery_reduction).

アップデート：BigInt のコードから始めると、手動で最適化された (そしてインライン化された) カラツバ乗算の 2 つのレベルを実行する価値があるように思えます (http://en.wikipedia.org/wiki/Karatsuba_algorithm)、その後のみ、BigInt で実装されている基数 32768 O(n^2) の乗算に戻ります。これにより、2048 ビット整数の乗算が 2.25 倍高速化されます。残念ながら、モジュロ演算は高速化されません。

アップデート：で定義された修正バレット削減を使用する http://www.lirmm.fr/arith18/papers/hasenpLaugh-FastModularReduction.pdf およびカラツバ乗算および事前計算能力 (で定義されている) http://www.ccrwest.org/gordon/fast.pdf)、Firefox 3.0 では、1 回の乗算に必要な時間を 73 秒から 12.3 秒に短縮できました。これが私にできる最善のことのように思えますが、それでも遅すぎます。

アップデート：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 とほぼ同じ速度なので、使用する価値はありません。

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

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

<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>

誰かこのコードを Silverlight (C#) に翻訳できますか?

役に立ちましたか？

解決

Java アプレットや Flash ムービーなど、JS から呼び出し可能な他のクライアント側テクノロジは受け入れられますか?BigIntの アプローチ すでにかなり速いです。BigInt を微調整するか、 異なるアルゴリズム, しかし、おそらく桁違いの改善は得られないでしょう。

他のヒント

モジュラー (mod) には「%」を使用し、整数の除算には「/」を使用します。関数 f(p,g,x,r) で、r<p および g<p という条件で (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
}

このルーチンにはもう少し多くの計算が含まれますが、各整数は 4096 ビット未満であり、通常は g^x よりもはるかに小さくなります。これは直接計算するよりも効率的であると思います。また、g^(i+1) を計算したため、g^(x%i) をより高速に計算できることにも注意してください。

編集：見る この郵便受け. 。Mehrdad は正しい (そしてより良い) 解決策を提供します。

C などのより適切な言語を使用して、ある種の Web サービスでサーバー側でそれを実行してはどうでしょうか?時間は、1 往復の時間 (9 秒未満) に、サーバーがネイティブ コードで BigInt ライブラリを使用して結果を計算する時間を加えたものになります。これはおそらくはるかに高速になるでしょう。

このモンゴメリモジュラーリダクションを試してください。 http://code.google.com/p/bi2php/ JavaScriptで。

変更した BigInt ライブラリのソース コードを拝見したい​​のですが、どこかで入手できますか?

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top