多項式基底

数学の分野において、多項式基底（たこうしききてい、英: polynomial basis）は、有限体の有限次拡大に対するある基底である。

α ∈ GF(p^m) を、GF(p) 上の次数 m のある原始多項式の根とする。すると、GF(p^m) の多項式基底は

\{1,\alpha ,\ldots ,\alpha ^{m-1}\}

^[1]

で与えられる。

加法[編集]

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

(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} となる。
拡張ユークリッドの互除法（英語版）
伊東-辻井のアルゴリズム（英語版）

使用法[編集]

多項式基底は、楕円曲線暗号のような離散対数問題に基づく、暗号理論的な応用の場面において頻繁に用いられる。

多項式基底を用いる利点として、乗算が比較的簡単であることが挙げられる。それとは対照的に、多項式基底の代わりとなる正規基底はより乗算が複雑となるが、自乗は非常に簡単となる。多項式基底のハードウェア実行は、正規基底によるものよりも大抵算術的により多くのパワーを消費する。

参考文献[編集]

^ Roman, Steven (1995). Field Theory. New York: Springer-Verlag. ISBN 0-387-94407-9
^ Huapeng, Wu (2001). "Selected Areas in Cryptography: 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14–15, 2000," (Document). Springer. p. 118. {{cite document}}: 不明な引数|contribution=は無視されます。 (説明)