原始多項式
テンプレート:About 数学の一分野である体論における原始多項式（げんしたこうしき、テンプレート:Lang-en-short）とは，有限体の拡大体 GF(pm)の原始元の最小多項式のことである． すなわち，テンプレート:Nowrapの元を係数とする次数 m の多項式 F(X) が， GF(pm) の原始元 α を根に持つ（つまり，F(α)=0 となる）とき，F(X) は原始多項式である． ここで，GF(pm)の原始元とは，体 GF(pm) において，集合 テンプレート:Nowrap が GF(pm) 自身と等しくなる元 α であり，GF(pm)における[[1の冪根|単位元1の (テンプレート:Nowrap)乗根]]である.
性質
全ての最小多項式は既約であるから，原始多項式は既約である．
原始多項式の定数項の係数は非零でなければならない．そうでないと，多項式 x で割り切れてしまう． GF(2)においては，テンプレート:Nowrap は原始多項式であるが，それ以外の全ての原始多項式は奇数個の項を持つ．なぜなら，偶数個の項を持つ多項式は，mod 2 では必ず多項式 (x + 1) で割り切れてしまう（すなわち x= 1 を根として持つ）．
p が素数であるとき，GF(p) 上の m 次の既約多項式 F(x) が原始多項式であるための条件は， テンプレート:Nowrap がF(x) で割り切れるような 最小の正整数 n が テンプレート:Nowrapであることである．
GF(p) 上の m 次の原始多項式は，ちょうど テンプレート:Nowrap 個存在する．ただし，φ はオイラーのφ関数である．
m 次の原始多項式は，GF(pm) において m 個の異なる根を持ち，全ての根の位数は テンプレート:Nowrapである．すなわち，α が根であるならば，テンプレート:Nowrap かつ 全ての i = 1, 2, ... ,pm - 2 においてテンプレート:Nowrap が成り立つ．
GF(pm) における原始元 α が，m 次の原始多項式 F(x) の根であるならば，この多項式は テンプレート:Nowrap で書き表せる．
利用方法
体の元の表現
原始多項式は， 有限体の元を表現するのに用いられる．もし GF(pm) の元 α が 原始多項式 F(x) の根ならば，α の位数は テンプレート:Nowrap であり，全ての GF(pm) の（0以外の）元は α のべき乗で表すことができる．つまり，
これらの元を多項式F(α)で割った余りを取ると，体の全ての元の多項式基底表現が得られる．
有限体の乗法群は常に巡回群であるため， GF(p)[x]/f(x) において， 原始多項式 f は，乗法群の生成元 x に関する多項式である．
疑似ランダムビット生成
GF(2) 上の原始多項式は，線形帰還シフトレジスタ(LFSR)を用いた疑似ランダムビット生成に利用できる．レジスタ長が n のLFSRの周期は最長で テンプレート:Nowrap であるが、全ての最長周期のLFSRは原始多項式を使って構築できる．[1]
例えば，原始多項式 テンプレート:Nowrap が与えられたとき，まずユーザが決めた10ビットのシード（全てが0であるものを除く）から始める．右から順に1番目のビット，2番目のビット，...，10番目のビットとする．ここで、シードはランダムに選ばれている必要はないが，ランダムでもよい．次に，10番目と3番目のビットの排他的論理和を計算し，これを0番目のビットとする．そして，10番目のビットを出力するとともに、シードのビットを１つずつ左へずらす。つまり、9番目のビットを10番目のビットに、8番目のビットを9番目のビットに、と順にずらして0番目のビットを1番目とする．このプロセスを繰り返すことにより，長さ テンプレート:Nowrap のビット列を生成できる．
一般に，GF(2) 上の m 次の原始多項式を用いると，このプロセスで周期がテンプレート:Nowrap である疑似ランダムなビット列を生成できる．
CRC コード
巡回冗長検査(CRC)は，誤り検出符号の一つであり，メッセージのビット列を GF(2) 上の多項式の係数と解釈して，特定のGF(2)上の生成多項式で割り算することで符号を生成する．詳細は巡回冗長検査を参照のこと．原始多項式，あるいはその積は，時として生成多項式の良い候補になる．これを利用すると，メッセージ中の離れた場所（原始多項式の次数がnであるとき，最大でテンプレート:Nowrap 離れたところ）に発生する2ビットのエラーを，確実に検出することができる．
原始三項式
非零の項が3つだけの原始多項式 テンプレート:Nowrap は有用であり，原始三項式と呼ばれる．多項式がシンプルなため，小さくて速いCRCコードが作れる．三項式の原始性（どの r と k を選べば原始三項式になるか）についての研究成果が知られている．
GF(2)上の多項式については，テンプレート:Nowrap がメルセンヌ素数ならば，r 次の既約多項式は必ず原始多項式である．（多項式が既約であり原始多項式ではないのは，多項式の根の周期が テンプレート:Nowrap の非自明な約数である場合だけである．一方，素数は非自明な約数を持たないため，この性質が導ける．）擬似乱数列生成器であるメルセンヌ・ツイスタは三項式は使わないが，この性質を利用している．
Richard Brentは原始三項式をリストしており，例えば テンプレート:Nowrap[2][3]がある．これは，巨大な周期 テンプレート:Nowrap ≒ 1022338617 を持つ疑似乱数生成に使われる．
脚注
外部リンク
- ↑ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
- ↑ Search for Primitive Trinomials (mod 2)
- ↑ テンプレート:Cite arxiv