4

計算できるようになりたい

g^x = g * g * g * ... * g     (x times)

ここで、gは有限体GF（2 ^ m）にあります。ここで、mはかなり大きく、m = 256、384、512などであるため、ルックアップテーブルは解決策ではありません。同様のアイデア、Z / nZ用のmodpow（ HACの619〜620ページを参照）には非常に高速なアルゴリズムがあることを私は知っています。

  1. サイクル（つまりg ^ x）を計算するための高速で非テーブルベースの方法は何ですか？
  2. これは間違いなく希望に満ちた質問ですが、ここに来ます。モンゴメリの乗算/べき乗のアイデアをガロア体に「リサイクル」できるでしょうか。同型性があるのでそう思いたいのですが、よくわかりません。

備考：これはmath.stackoverflow.comへの私の投稿からのものです。これがこの質問をするのに最適なコミュニティだと思います。

4

1 に答える 1

3

数学のstackexchangeコミュニティから、2人にBinaryExponentiaionを提案してもらいました。ウィキペディアは、再帰的アルゴリズムとして再帰的であると述べています。Wikiの擬似コードに示されているように、反復アルゴリズムに変更できます。

最初はそのアイデアに眉をひそめましたが、さらに調べてみると、モンゴメリ乗算を使用するガロア有限体でのバイナリべき乗の実装に役立つ2つの論文（1、2 ）が 見つかりました。

さらに、Jyrki Lahtonenは、乗算を高速化するために、通常の基数（または、m = / = 256、384、512などの最適な通常の基数）を使用することを提案しました。この乗算方法のアルゴリズムは、このペーパーに記載されています。

彼/彼女の入力のためのサーノルドに感謝します。

于 2012-07-24T22:33:19.850 に答える