原始多項式（場の理論）

数学の一分野である有限体理論において、原始多項式は有限体GF( p ^m )の原始元の最小多項式である。つまり、GF( p ) = Z / p Zに係数を持つm次多項式F ( X )は、モニックでありGF( p ^m )に根α を持ち、 が体GF( p ^m )全体である場合に原始多項式である。つまり、α はGF( p ^m )の原始 ( p ^m − 1 ) 根である。 ${\displaystyle \{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}}$

• すべての最小多項式は既約なので、すべての原始多項式も既約です。
• 原始多項式は、ゼロでない定数項を持たなければなりません 。そうでなければ、 xで割り切れません。GF (2)では、x + 1は原始多項式であり、他のすべての原始多項式は項数が奇数です。これは、項数が偶数である 2 を法とする多項式はx + 1で割り切れる(根が 1 である) ためです。
• GF( p )上のm次の既約多項式 F ( x ) ^（ pは素数）は、 F ( x )がxn−1を割り切る最小の正の整数nがn = pm −1であるとき原始多項式と^呼ばれる。
• m次原始多項式はGF( p ^m )にm 個の異なる根を持ち、それらはすべてp ^m − 1 の位数を持ち、つまりそれらのいずれも体の乗法群を生成する。
• GF( p )上にはちょうどφ ( p ^m − 1)個の原始元とφ ( p ^m − 1)/ m個の原始多項式があり、それぞれ次数mである。ここでφはオイラーのトーティエント関数である。^[1]
• GF( p ^m )の原始元αの代数共役はα、α ^p、α ^{p 2}、 …、α ^{p m −1}であり、したがって原始多項式F ( x )は明示的な形式F ( x ) = ( x − α ) ( x − α ^p ) ( x − α ^{p 2} ) … ( x − α ^{p m −1} )を持ちます。この形式の多項式の係数が、必ずしも原始的ではないGF( p ⁿ )の任意のαに対してGF( p )に含まれることは、多項式がその係数にフロベニウス自己同型を適用して不変であるという性質( α ^{p n} = αを使用) と、フロベニウス自己同型の固定体がGF( p )であるという事実から生じます。

GF(3)上では、多項式x ² + 1は既約ですが、 x ⁴ − 1 を割り切るので原始的ではありません。その根は 4 次巡回群を生成し、GF(3 ² )の乗法群は 8 次巡回群です。一方、多項式x ² + 2 x + 2は原始的です。その根の 1 つをαで表します。すると、 3 ² − 1 = 8より小さく互いに素な自然数は1、3、5、7 なので、GF(3 ² )の 4 つの原始根はα、α ³ = 2 α + 1、α ⁵ = 2 α、α ⁷ = α + 2です。原始根αとα ^{3 は}代数的に共役です。実際、x ² + 2 x + 2 = ( x − α ) ( x − (2 α + 1))です。残りの原始根α ⁵とα ⁷ = ( α ⁵ ) ³も代数的に共役であり、2 番目の原始多項式x ² + x + 2 = ( x − 2 α ) ( x − ( α + 2))を生成します。

3 次では、GF(3 ³ )にはφ (3 ³ − 1) = φ (26) = 12個の原始元がある。3 次原始多項式にはそれぞれ 3 つの根があり、すべて必ず原始根となるため、3 次原始多項式は12 / 3 = 4 個ある。1 つの原始多項式はx ³ + 2 x + 1である。その根の 1 つをγで表すと、代数的に共役な元はγ ³とγ ^{9である。他の原始多項式は、他の原始元}γ ^r上に構築された代数的に共役な集合に関連付けられており、 rは26 と互いに素である。

${\displaystyle {\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}}$

原始多項式は有限体の元を表すために使用できます。GF ( p ^m ) のα が原始多項式F ( x )の根である場合、GF( p ^m )の非ゼロ元はαの連続するべき乗として表されます。

${\displaystyle \mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.}$

これにより、コンピュータ内で有限体の非ゼロ元を、対応する指数で表すことで経済的に表現することができる。この表現は、指数を法として加算するのに相当するため、乗算が容易になる。${\displaystyle \alpha .}$ ${\displaystyle p^{m}-1.}$

2つの元を持つ体GF(2)上の原始多項式は、疑似乱数ビット生成に使用できます。実際、最大サイクル長（2 ⁿ − 1、nは線形フィードバックシフトレジスタの長さ）を持つすべての線形フィードバックシフトレジスタは、原始多項式から構築できます。^[2]

一般に、GF(2)上のm次の原始多項式の場合、このプロセスは同じシーケンスを繰り返す前に2 ^m − 1個の疑似乱数ビット を生成します。

巡回冗長検査(CRC) は、メッセージ ビット文字列を GF(2) 上の多項式の係数として解釈し、それを同じく GF(2) 上の固定生成多項式で割ることによって動作するエラー検出コードです。CRCの数学を参照してください。原始多項式、またはその倍数は、メッセージ ビット文字列内で離れた場所で発生する 2 つのビット エラー (次数nの原始多項式の場合、距離2 ⁿ − 1まで) を確実に検出できるため、生成多項式として適している場合があります。

原始多項式の有用なクラスは、3つの非ゼロ項x ^r + x ^k + 1のみを持つ原始三項式です。その単純さにより、特に小型で高速な線形フィードバックシフトレジスタが実現します。^[3] 多くの結果から、三項式の原始性を特定してテストする手法が示されています。^[4]

GF(2) 上の多項式（2 ^r − 1はメルセンヌ素数）の場合、次数rの多項式は、それが既約である場合に限り原始多項式となります。（既約多項式が与えられた場合、xの周期が2 ^r − 1の非自明な因数である場合にのみ原始多項式ではありません。素数には非自明な因数はありません。）メルセンヌツイスター疑似乱数生成器は三項式を使用しませんが、これを利用します。

リチャード・ブレントは、この形式の原始三項式、例えばx ^74207281 + x ^30684570 + 1を表にまとめている。^{[5] [6]これを使って、巨大な周期}2 ^74207281 − 1 ≈の疑似乱数生成器を作成することができる。3 × 10 ^{22 338 617} .

• ワイスタイン、エリック W.「原始多項式」。マスワールド。