多項式基底のソースを表示

[[数学]]の分野において、'''多項式基底'''（たこうしききてい、{{Lang-en-short|polynomial basis}}）は、[[有限体]]の[[体の拡大|有限次拡大]]に対するある[[基底 (線型代数学)|基底]]である。

α ∈ [[有限体|GF(''p''<sup>''m''</sup>)]] を、GF(''p'') 上の次数 ''m'' のある{{仮リンク|原始多項式 (体論)|label=原始多項式|en|primitive polynomial (field theory)}}の根とする。すると、GF(''p''<sup>''m''</sup>) の多項式基底は

:<math>
\{ 1, \alpha, \ldots, \alpha^{m-1}\}
</math> <ref>
{{cite book | last = Roman | first = Steven | authorlink = :en:Steven Roman | title = Field Theory | publisher = Springer-Verlag | year = 1995 | location = New York | isbn = 0-387-94407-9 }}
</ref>

で与えられる。

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

:<math>(2\alpha^2 + 2\alpha + 1) + (2\alpha + 2) = 2\alpha^2 + 4\alpha + 3 = 2\alpha^2 + \alpha</math>

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

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

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

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

== 自乗 ==
自乗は、一般的な指数関数や逆元に対して用いられるため、重要な演算である。多項式基底におけるある元を自乗するための最も基本的な方法は、ある元の上で選ばれた乗法アルゴリズムを二度行うことであろう。一般的な場合、特に、ある元にそれ自身を掛ける際にはすべてのビットが等しくなるという事実と関係して、いくつかのマイナーな最適化が存在する。実際は、しかしながら、GF(2<sup>''m''</sup>) の多項式基底における自乗を乗算よりもより簡単にするようなとても小さな非ゼロの系数を伴う、[[既約多項式]]が体に対して選ばれる<ref>{{Citation2 |df=ja | last1 = Huapeng | first1 = Wu | contribution = On Complexity of Polynomial Basis Squaring in F(2<sup>m</sup>) | title = Selected Areas in Cryptography: 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14–15, 2000,  | publisher = Springer | pages = 118 | year = 2001 | postscript = <!--None--> }}</ref>。

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

* [[ルックアップテーブル]] &mdash; 繰り返しになるが、小さな体でのみ有効で、そうでない場合には実行するにはテーブルが大きくなり過ぎてしまう。
* [[部分体]]の逆 &mdash; 方程式系を部分体において解くことで可能となる。
* 自乗と乗算の繰り返し &mdash; 例えば、GF(2<sup>''m''</sup>) においては ''A''<sup>&minus;1</sup> = ''A''<sup>2''m'' &minus; 2</sup> となる。
* {{仮リンク|拡張ユークリッドの互除法|en|extended euclidean algorithm}}
* {{仮リンク|伊東-辻井のアルゴリズム|en|Itoh-Tsujii inversion algorithm}}

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

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

== 参考文献 ==
<references/>

== 関連項目 ==
* [[正規基底]]
* [[双対基底]]
* [[基底変換]]

{{DEFAULTSORT:たこうしききてい}}
[[Category:線型代数学]]
[[Category:体論]]
[[Category:暗号技術]]
[[Category:数学に関する記事]]