多項式基底

多項式基底を用いた加法は、p を法とする加法と同程度簡単なものである。例えば、GF(3^m) においては、

${\displaystyle (2\alpha ^{2}+2\alpha +1)+(2\alpha +2)=2\alpha ^{2}+4\alpha +3=2\alpha ^{2}+\alpha }$

が成立する。GF(2^m) においては、2 を法とする加法と減法が同じものであるため、加法は特に簡単となる。さらに、この作用は基本的なXOR論理ゲートを用いるハードウェアにおいて実行することが出来る。

多項式基底における二つの元の乗法は、通常の乗法のやり方と同様に行うことが出来る。しかし、特にハードウェアにおいて、乗法の計算のスピードを上げる多くの方法が存在する。GF(p^m) 内の二つの元を掛け合わせる直接的な方法を使う際は、GF(p) における最大 m² 回の乗算と、GF(p) における最大 m² − m の加算が必要となる。

それらの値を減らすためのいくつかの方法として、以下のようなものが挙げられる：

• ルックアップテーブル — 結果を事前にまとめておいたテーブルで、主に小さい体において用いられる。そうでない場合、実行するにはテーブルが大きくなり過ぎてしまう。
• カラツバ法
• 線形帰還シフトレジスタに基づく乗算
• 部分体計算
• パイプライン乗算器
• シストリック乗算器

自乗は、一般的な指数関数や逆元に対して用いられるため、重要な演算である。多項式基底におけるある元を自乗するための最も基本的な方法は、ある元の上で選ばれた乗法アルゴリズムを二度行うことであろう。一般的な場合、特に、ある元にそれ自身を掛ける際にはすべてのビットが等しくなるという事実と関係して、いくつかのマイナーな最適化が存在する。実際は、しかしながら、GF(2^m) の多項式基底における自乗を乗算よりもより簡単にするようなとても小さな非ゼロの系数を伴う、既約多項式が体に対して選ばれる^[2]。

元の逆は、以下に記すような多くの方法によって得ることが出来る：

• ルックアップテーブル — 繰り返しになるが、小さな体でのみ有効で、そうでない場合には実行するにはテーブルが大きくなり過ぎてしまう。
• 部分体の逆 — 方程式系を部分体において解くことで可能となる。
• 自乗と乗算の繰り返し — 例えば、GF(2^m) においては A⁻¹ = A^{2m − 2} となる。
• 拡張ユークリッドの互除法（英語版）
• 伊東-辻井のアルゴリズム（英語版）