原始多項式のソースを表示

{{about||係数の[[最大公約数]]が 1 の多項式|原始多項式 (環論)}}
[[数学]]の一分野である[[体論]]における'''原始多項式'''（げんしたこうしき、{{lang-en-short|''primitive polynomial''}}）とは，[[有限体]]の[[体の拡大|拡大体]] GF(''p''<sup>''m''</sup>)の[[原始元 (有限体)|原始元]]の[[最小多項式 (体論)|最小多項式]]のことである．
すなわち，{{nowrap|1=GF(''p'') = '''Z'''/''p'''''Z'''}}の元を係数とする次数 ''m'' の多項式 ''F''(''X'') が， GF(''p''<sup>''m''</sup>) の原始元 ''α'' を根に持つ（つまり，''F''(''α'')=0 となる）とき，''F''(''X'') は原始多項式である．
ここで，GF(''p''<sup>''m''</sup>)の原始元とは，体 GF(''p''<sup>''m''</sup>) において，集合 {{nowrap|{0, 1, ''α'', ''α''{{i sup|2}}, ''α''{{i sup|3}}, ..., ''α''{{i sup|''p''{{sup|''m''}}-2}}}{{null}}}} が GF(''p''<sup>''m''</sup>) 自身と等しくなる元 ''α'' であり，GF(''p''<sup>''m''</sup>)における[[1の冪根|単位元1の ({{nowrap|''p''<sup>''m''</sup> - 1}})乗根]]である.

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

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

''p'' が素数であるとき，GF(''p'') 上の ''m'' 次の既約多項式 ''F''(''x'') が原始多項式であるための条件は，
{{nowrap|''x''<sup>''n''</sup> - 1}} が''F''(''x'') で割り切れるような
最小の正整数 ''n'' が {{nowrap|1=''n'' = ''p''<sup>''m''</sup> -1}}であることである．

GF(''p'') 上の ''m'' 次の原始多項式は，ちょうど {{nowrap|''φ''(''p''<sup>''m''</sup> - 1)/''m''}} 個存在する．ただし，''φ'' は[[オイラーのφ関数]]である．

''m'' 次の原始多項式は，GF(''p''<sup>''m''</sup>) において ''m'' 個の異なる根を持ち，全ての根の[[位数 (群論)|位数]]は {{nowrap|''p''<sup>''m''</sup> - 1}}である．すなわち，''α'' が根であるならば，{{nowrap|1=''α''{{i sup|''p''{{sup|''m''}}-1}} = 1}} かつ 全ての ''i'' = 1, 2, ... ,''p''<sup>''m''</sup> - 2 において{{nowrap|''α''{{i sup|''i''}} ≠ 1}} が成り立つ．

GF(''p''<sup>''m''</sup>) における原始元 ''α'' が，''m'' 次の原始多項式 ''F''(''x'') の根であるならば，この多項式は {{nowrap|1=''F''(''x'') = (''x'' - ''α'')(''x'' - ''α''{{i sup|''p''}})(''x'' - ''α''{{i sup|''p''{{sup|2}}}})...(''x'' - ''α''{{i sup|''p''{{sup|''m''-1}}}})}} で書き表せる．

==利用方法==
===体の元の表現===
原始多項式は， [[有限体]]の元を表現するのに用いられる．もし GF(''p''<sup>''m''</sup>) の元 ''α'' が 原始多項式 ''F''(''x'') の根ならば，''α'' の位数は {{nowrap|''p''<sup>''m''</sup> - 1}} であり，全ての GF(''p''<sup>''m''</sup>) の（0以外の）元は ''α'' のべき乗で表すことができる．つまり，

:<math>
\mathrm{GF}(p^m) = \{ 0, 1, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} 
</math>

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

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

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

例えば，原始多項式 {{nowrap|''x''<sup>10</sup> + ''x''<sup>3</sup> + 1}} が与えられたとき，まずユーザが決めた10ビットのシード（全てが0であるものを除く）から始める．右から順に1番目のビット，2番目のビット，...，10番目のビットとする．ここで、シードはランダムに選ばれている必要はないが，ランダムでもよい．次に，10番目と3番目のビットの[[排他的論理和]]を計算し，これを0番目のビットとする．そして，10番目のビットを出力するとともに、シードのビットを１つずつ左へずらす。つまり、9番目のビットを10番目のビットに、8番目のビットを9番目のビットに、と順にずらして0番目のビットを1番目とする．このプロセスを繰り返すことにより，長さ {{nowrap|1=2<sup>10</sup> - 1 = 1023}} のビット列を生成できる．

一般に，GF(2) 上の ''m'' 次の原始多項式を用いると，このプロセスで周期が{{nowrap|2<sup>''m''</sup> - 1}} である疑似ランダムなビット列を生成できる．

=== CRC コード ===

[[巡回冗長検査]](CRC)は，誤り検出符号の一つであり，メッセージのビット列を GF(2) 上の多項式の係数と解釈して，特定のGF(2)上の生成多項式で割り算することで符号を生成する．詳細は[[巡回冗長検査]]を参照のこと．原始多項式，あるいはその積は，時として生成多項式の良い候補になる．これを利用すると，メッセージ中の離れた場所（原始多項式の次数が''n''であるとき，最大で{{nowrap|2<sup>''n''</sup> - 1}} 離れたところ）に発生する2ビットのエラーを，確実に検出することができる．

==原始三項式==

非零の項が3つだけの原始多項式 {{nowrap|''x<sup>r</sup>'' + ''x<sup>k</sup>'' + 1}} は有用であり，原始[[三項式]]と呼ばれる．多項式がシンプルなため，小さくて速い[[巡回冗長検査|CRCコード]]が作れる．三項式の原始性（どの ''r'' と ''k'' を選べば原始三項式になるか）についての研究成果が知られている．

GF(2)上の多項式については，{{nowrap|2<sup>''r''</sup> - 1}} が[[メルセンヌ数|メルセンヌ素数]]ならば，''r'' 次の既約多項式は必ず原始多項式である．（多項式が既約であり原始多項式ではないのは，多項式の根の周期が {{nowrap|2<sup>''r''</sup> - 1}} の非自明な約数である場合だけである．一方，素数は非自明な約数を持たないため，この性質が導ける．）擬似乱数列生成器である[[メルセンヌ・ツイスタ]]は三項式は使わないが，この性質を利用している．

[[Richard Brent (scientist)|Richard Brent]]は原始三項式をリストしており，例えば {{nowrap|''x''<sup>74207281</sup> + ''x''<sup>30684570</sup> + 1}}<ref>[http://wwwmaths.anu.edu.au/~brent/trinom.html Search for Primitive Trinomials (mod&nbsp;2)]</ref><ref>{{cite arxiv |title=Twelve new primitive binary trinomials |first1=Richard P. |last1=Brent |authorlink1=Richard Brent (scientist) |first2=Paul |last2=Zimmerman |arxiv=1605.09213 |class=math.NT |date=24 May 2016 }}</ref>がある．これは，巨大な周期 {{nowrap|2<sup>74207281</sup> - 1}} ≒ 10<sup>22338617</sup> を持つ疑似乱数生成に使われる．

==脚注==
{{reflist}}

==外部リンク==
* {{MathWorld |urlname=PrimitivePolynomial |title=Primitive Polynomial}}

{{DEFAULTSORT:けんしたこうしき}}
[[Category:体論]]
[[Category:多項式]]
[[Category:数学に関する記事]]