多項式基底

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

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

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

[1]

で与えられる。

加法[編集]

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

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

乗法[編集]

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

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

自乗[編集]

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

[編集]

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

使用法[編集]

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

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

参考文献[編集]

  1. ^ Roman, Steven (1995). Field Theory. New York: Springer-Verlag. ISBN 0-387-94407-9. 
  2. ^ Huapeng, Wu (2001年). “On Complexity of Polynomial Basis Squaring in F(2m)”. Selected Areas in Cryptography: 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14–15, 2000,. Springer. pp. 118 

関連項目[編集]