原始多項式

数学の一分野である体論における原始多項式（げんしたこうしき、）とは，有限体の拡大体 GF(pm)の原始元の最小多項式のことである．
すなわち，の元を係数とする次数 m の多項式 F(X) が， GF(pm) の原始元 α を根に持つ（つまり，F(α)=0 となる）とき，F(X) は原始多項式である．
ここで，GF(pm)の原始元とは，体 GF(pm) において，集合  が GF(pm) 自身と等しくなる元 α であり，GF(pm)における単位元1の ()乗根である.

性質
全ての最小多項式は既約であるから，原始多項式は既約である．

原始多項式の定数項の係数は非零でなければならない．そうでないと，多項式 x で割り切れてしまう．
GF(2)においては， は原始多項式であるが，それ以外の全ての原始多項式は奇数個の項を持つ．なぜなら，偶数個の項を持つ多項式は，mod 2 では必ず多項式 (x + 1) で割り切れてしまう（すなわち x= 1 を根として持つ）．

p が素数であるとき，GF(p) 上の m 次の既約多項式 F(x) が原始多項式であるための条件は，
 がF(x) で割り切れるような
最小の正整数 n が であることである．

GF(p) 上の m 次の原始多項式は，ちょうど  個存在する．ただし，φ はオイラーのφ関数である．

m 次の原始多項式は，GF(pm) において m 個の異なる根を持ち，全ての根の位数は である．すなわち，α が根であるならば， かつ 全ての i = 1, 2, ... ,pm - 2 において が成り立つ．

GF(pm) における原始元 α が，m 次の原始多項式 F(x) の根であるならば，この多項式は  で書き表せる．

利用方法
体の元の表現
原始多項式は， 有限体の元を表現するのに用いられる．もし GF(pm) の元 α が 原始多項式 F(x) の根ならば，α の位数は  であり，全ての GF(pm) の（0以外の）元は α のべき乗で表すことができる．つまり，

これらの元を多項式F(α)で割った余りを取ると，体の全ての元の多項式基底表現が得られる．

有限体の乗法群は常に巡回群であるため，
GF(p)[x]/f(x) において，
原始多項式 f は，乗法群の生成元 x に関する多項式である．

疑似ランダムビット生成
GF(2) 上の原始多項式は，線形帰還シフトレジスタ(LFSR)を用いた疑似ランダムビット生成に利用できる．レジスタ長が n のLFSRの周期は最長で  であるが、全ての最長周期のLFSRは原始多項式を使って構築できる．C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners

例えば，原始多項式  が与えられたとき，まずユーザが決めた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は原始三項式をリストしており，例えば Search for Primitive Trinomials (mod 2)がある．これは，巨大な周期  ≒ 1022338617 を持つ疑似乱数生成に使われる．

脚注

外部リンク


Category:体論
Category:多項式
Category:数学に関する記事