原始多項式原始多項式の概要

性質

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

原始多項式の定数項の係数は非零でなければならない．そうでないと，多項式 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]。

[前の解説]

[続きの解説]

「原始多項式」の続きの解説一覧

1 原始多項式とは
2 原始多項式の概要
3 外部リンク

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

原始多項式 原始多項式の概要