原始多項式

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