5

F := GF(p^n) が p^n 個の要素を持つ有限体である場合、p は素数、na は自然数ですが、F の 2 つの要素の積を計算する効率的なアルゴリズムはありますか?

これまでの私の考えは次のとおりです。

F の標準的な構成は、GF(p) の次数 n の既約多項式 f を取り、F の元を商 GF(p)[X]/(f) の多項式と見なすことであることを知っています。多項式の乗算と加算は簡単に実装できるはずなので、これはおそらくすでに正しいアプローチであると感じていますが、どういうわけかこれが実際にどのように行われるのかわかりません。たとえば、適切な f をどのように選択し、任意の多項式の等価クラスを取得するにはどうすればよいでしょうか?

4

5 に答える 5

5

まず、GF[p] 上の次数 n の既約多項式を選択します。ランダムなものを生成するだけで、ランダムな多項式は確率 ~1/n で既約です。

ランダムな多項式をテストするには、GF[p] で多項式を因数分解するコードが必要です。いくつかのアルゴリズムについては、ウィキペディアのページを参照してください。

次に、GF[p^n] の要素は、GF[p] の n 次多項式です。通常の多項式演算を行い、既約多項式を法とする剰余を計算するようにしてください。

このスキームの単純なバージョンをコード化するのは非常に簡単です。モジュロ演算など、実装方法が複雑になる可能性があります。累乗剰余、モンゴメリ乗算、および FFT を使用した乗算を参照してください。

于 2010-01-03T02:09:15.720 に答える
3

GF（p ^ n）の要素を乗算する効率的なアルゴリズムがあるかどうかは、GF（p ^ n）の要素をどのように表現しているかによって異なります。

あなたが言うように、1つの方法は確かにGF（p）（X）/（f）で働くことです。ここでは、加算と乗算は比較的簡単です。ただし、適切な既約多項式fを決定することは簡単ではありません。私が知る限り、適切なfを計算するための効率的なアルゴリズムはありません。

もう1つの方法は、ツェッヒ対数と呼ばれるものを使用することです。 Magmaは、それらの事前に計算されたテーブルを使用して、小さな有限体を操作します。そのドキュメントはあまり明確ではありませんが、GAPもそうする可能性があります。

数学的構造を使用した計算は、多くの場合非常に注意が必要です。あなたは確かにここで明白な何かを見逃していません。

于 2009-12-20T15:01:50.513 に答える
3

それはあなたのニーズとあなたの分野に依存します。

乗算するときは、F xのジェネレーターを選択する必要があります。追加するときは、 F がより小さな F p m上のベクトル空間であるという事実を使用する必要があります。実際には、あなたが多くの時間を費やしているのは、いくつかの混合アプローチです。たとえば、F 256で作業している場合、F 256 xの生成元 X を取り、 G を F 16での最小多項式とします。あなたは今持っています

(sum i より小さい 16 a i X i )(sum j より小さい 16 b j X j )= sum_k sum i+j = k a i b j X i+j

乗算を効率的にするために必要なことは、F 16の乗算表を格納し、 (G を使用して) X の低べき乗と F 16の要素に関して X^m を構築することだけです。

最後に、p n = 2 2 nというまれなケースでは、非常に効率的なアルゴリズムが存在するコンウェイの体の数 (コンウェイの「勝利の方法」またはクヌースのボリューム 4A セクション 7.1.3 を参照) が得られます。

于 2009-12-21T10:35:35.387 に答える
2

ガロア体算術ライブラリ(C++、mod 2、他の素数要素をサポートしているようには見えません)

リンボックス(C++)

MPFQ (C++)

ただし、これらについて個人的な経験はありません（次数31以下のガロア体用に独自のプリミティブC++クラスを作成しましたが、エキゾチックすぎず、コピーする価値はありません）。言及されたコメント投稿者の 1 人のように、mathoverflow.netをチェックすることもできます。きちんと尋ねて、最初に宿題を済ませていることを確認してください。そこの誰かが、有限体の操作に適した数学ソフトウェアの種類を知っているべきであり、十分に述べられた質問が閉じられてはならないという mathoverflow の関心領域に十分近いものです。

于 2009-12-20T15:34:21.263 に答える
1

これは、モニック既約多項式 f(X) が識別されたときに、有限体で乗算を実行するアルゴリズムの問​​題であると仮定します (そうでない場合は、Rabin's Test for Ireducibility を検討してください) 。

次数 n-1 の 2 つの多項式があります。

A(X) = a_0 + a_1*X + a_2*X^2 + ... + a_(n-1)*X^(n-1) and
B(X) = b_0 + b_1*X + b_2*X^2 + ... + b_(n-1)*X^(n-1)

係数a_k, b_kはZ/pZの代表{0,1,...,p-1}から外れています。

製品は次のように定義されます。

C(X) = A(X)*B(X) % f(X),

ここで、モジュロ演算子 "%" は、多項式除算A(X)*B(X) / f(X)の剰余です。

以下は、複雑さO（n ^ 2）のアプローチです

1.) 分配法則により、製品は次のように分解できます。

  B(X) * X^(n-1) * a_(n-1)
+ B(X) * X^(n-2) * a_(n-2)
+ ...
+ B(X) * a_0

=

  (...(a_(n-1) * B(X)  * X 
   +  a_(n-2)  * B(X)) * X
   +  a_(n-3)  * B(X)) * X
   ...
   +  a_1      * B(X)) * X
   +  a_0      * B(X)

2.) %-演算子は Z/pZ[X] から GF(p^n) への環準同型であるため、上記の反復の各ステップで適用できます。

 A(X)*B(X) % f(X) =

  (...(a_(n-1) * B(X)  * X % f(X)
   +  a_(n-2)  * B(X)) * X % f(X)
   +  a_(n-3)  * B(X)) * X % f(X)
   ...
   +  a_1      * B(X)) * X % f(X)
   +  a_0      * B(X)

3.) Xとの各乗算、つまり係数空間でのシフトの後、要素t_kn * X^nを持つ次数nの多項式T_k(X)が得られます。f(X)を法とするリダクションは、

T_k(X) % f(X) = T_k(X) - t_kn*f(X),

これは次数 n-1 の多項式です。

最後に、還元多項式で

r(x) := f(x) - X^n  and

T_k(X) =: t_kn * X^n + U_(n-1)(X)

T_k(X) % f(X) = t_kn * X^n + U_(n-1)(X) - t_kn*( r(x) + X^n)
              = U_(n-1)(X) - t_kn*r(x)

つまり、すべてのステップは最大次数 n-1 の多項式で実行できます。

于 2021-03-27T01:19:16.397 に答える