原始多項式

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

性質[編集]

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

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

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

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

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

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

利用方法[編集]

体の元の表現[編集]

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

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

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

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

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

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

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

CRC コード[編集]

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

原始三項式[編集]

非零の項が3つだけの原始多項式 xr + xk + 1 は有用であり,原始三項式と呼ばれる.多項式がシンプルなため,小さくて速いCRCコードが作れる.三項式の原始性(どの rk を選べば原始三項式になるか)についての研究成果が知られている.

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

Richard Brentは原始三項式をリストしており,例えば x74207281 + x30684570 + 1[2][3]がある.これは,巨大な周期 274207281 - 1 ≒ 1022338617 を持つ疑似乱数生成に使われる.

脚注[編集]

  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]。

外部リンク[編集]