原始多項式

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

性質[編集]

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

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

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

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

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

GF(p^m) における原始元 α が，m 次の原始多項式 F(x) の根であるならば，この多項式は F(x) = (x - α)(x - α^p)(x - α^p²)...(x - α^{p^m-1}) で書き表せる．

利用方法[編集]

体の元の表現[編集]

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

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

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

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

疑似ランダムビット生成[編集]

GF(2) 上の原始多項式は，線形帰還シフトレジスタ(LFSR)を用いた疑似ランダムビット生成に利用できる．レジスタ長が n のLFSRの周期は最長で 2ⁿ - 1 であるが、全ての最長周期のLFSRは原始多項式を使って構築できる．^[1]

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

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

CRC コード[編集]

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

原始三項式[編集]

非零の項が3つだけの原始多項式 x^r + x^k + 1 は有用であり，原始三項式と呼ばれる．多項式がシンプルなため，小さくて速いCRCコードが作れる．三項式の原始性（どの r と k を選べば原始三項式になるか）についての研究成果が知られている．

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

Richard Brentは原始三項式をリストしており，例えば x^74207281 + x^30684570 + 1^[2]^[3]がある．これは，巨大な周期 2^74207281 - 1 ≒ 10^22338617 を持つ疑似乱数生成に使われる．

脚注[編集]

^ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
^ Search for Primitive Trinomials (mod 2)
^ Brent, Richard P.; Zimmerman, Paul (24 May 2016). "Twelve new primitive binary trinomials". arXiv:1605.09213 [math.NT]。

外部リンク[編集]

Weisstein, Eric W. "Primitive Polynomial". mathworld.wolfram.com (英語).

[1] C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners

[2] Search for Primitive Trinomials (mod 2)

[3] Brent, Richard P.; Zimmerman, Paul (24 May 2016). "Twelve new primitive binary trinomials". arXiv:1605.09213 [math.NT]。

[1]

[2]

[3]