原始多項式
GF(2) 上の原始多項式は,線形帰還シフトレジスタ(LFSR)を用いた疑似ランダムビット生成に利用できる.レジスタ長が n のLFSRの周期は最長で 2 - 1 であるが、全ての最長周期のLFSRは原始多項式を使って構築できる.
例えば,原始多項式 x + x + 1 が与えられたとき,まずユーザが決めた10ビットのシード(全てが0であるものを除く)から始める.右から順に1番目のビット,2番目のビット,...,10番目のビットとする.ここで、シードはランダムに選ばれている必要はないが,ランダムでもよい.次に,10番目と3番目のビットの排他的論理和を計算し,これを0番目のビットとする.そして,10番目のビットを出力するとともに、シードのビットを1つずつ左へずらす。つまり、9番目のビットを10番目のビットに、8番目のビットを9番目のビットに、と順にずらして0番目のビットを1番目とする.このプロセスを繰り返すことにより,長さ 2 - 1 = 1023 のビット列を生成できる.
一般に,GF(2) 上の m 次の原始多項式を用いると,このプロセスで周期が2 - 1 である疑似ランダムなビット列を生成できる.
非零の項が3つだけの原始多項式 x + x + 1 は有用であり,原始三項式と呼ばれる.多項式がシンプルなため,小さくて速いCRCコードが作れる.三項式の原始性(どの r と k を選べば原始三項式になるか)についての研究成果が知られている.
GF(2)上の多項式については,2 - 1 がメルセンヌ素数ならば,r 次の既約多項式は必ず原始多項式である.(多項式が既約であり原始多項式ではないのは,多項式の根の周期が 2 - 1 の非自明な約数である場合だけである.一方,素数は非自明な約数を持たないため,この性質が導ける.)擬似乱数列生成器であるメルセンヌ・ツイスタは三項式は使わないが,この性質を利用している.
Richard Brentは原始三項式をリストしており,例えば x + x + 1がある.これは,巨大な周期 2 - 1 ≒ 10 を持つ疑似乱数生成に使われる.