生成多項式

質問

生成多項式、既約多項式とは何かを教えてください。
あと、擬似乱数係数とは何かも教えてください。
それからできればKASAMI係数とは何かも教えてください。

回答No.6

nuubou

うっかりして生成多項式のことを原始多項式だと思っていました

生成多項式：
Ｋを体としｘを変数としｎを自然数としｆ（ｘ）を「Ｋの元を係数とするｎ次多項式」としＮをｎより大きい自然数としπを「Ｋの元を係数とする次数がＮ未満の多項式のうちｆ（ｘ）で割り切れる多項式の集合」としたときｆ（ｘ）をπの生成多項式という

既約多項式：
Ｋを体としｘを変数としｎを自然数としｆ（ｘ）をＫの元を係数とするｎ次多項式としたときｆ（ｘ）＝０の根がＫに含まれないときｆ（ｘ）を既約多項式という

原始多項式：
ｑを自然数としＫをｑ個の元からなる体としｘを変数としｎを自然数としｆ（ｘ）をＫの元を係数とするｎ次多項式とし自然数ｍに対してｘ＾ｍをｆ（ｘ）で割ったときの余りの多項式を［ｘ＾ｍ］としたとき
［ｘ＾０］，［ｘ＾１］，［ｘ＾２］，・・・，［ｘ＾（ｑ＾ｎ－２）］
がすべて異なるときｆ（ｘ）を原始多項式という

疑似乱数：
ｑを自然数としＫをｑ個の元からなる体としｘを変数としｎを自然数としｆ（ｘ）をＫの元を係数とするｎ次原始多項式とし自然数ｍに対してｘ＾ｍをｆ（ｘ）で割ったときの余りの多項式を［ｘ＾ｍ］とし自然数ｍに対して［ｘ＾ｍ］の係数を最低次からｎ個並べてできたベクトルをｖ（［ｘ＾ｍ］）としたとき無限のベクトル列
ｖ（［ｘ＾０］），ｖ（［ｘ＾１］），ｖ（［ｘ＾２］），・・・
を疑似乱数という

Ｋを最も小さい体｛０，１｝としｎ＝４としたとき
ｘ＾４＋ｘ＋１は既約多項式であり原始多項式だが
ｘ＾４＋ｘ＾３＋ｘ＾２＋ｘ＋１は既約多項式であるが原始多項式ではない
両方とも０，１いずれを代入しても１でありＫ内に根を持たないから両方とも既約多項式であることは明らか
ｘ＾５を下の式で割ったときの余りが１であるから下の式は原始多項式ではないことが明らか

ｎ次の多項式により生成される疑似乱数はｑ＾ｎ－１個の異なるベクトルをｑ＾ｎ－１の周期で順次発生する
ｎ＝１６，ｑ＝２とすれば６５５３５のベクトルを６５５３５の周期で順次発生することになります　すごいですね！

ｑ＝２の場合には発生装置が簡単な論理回路で構成できます
［ｘ＾ｍ］のｎ－１次の係数が０の場合には
［ｘ＾（ｍ＋１）］＝ｘ・［ｘ＾ｍ］となり
［ｘ＾ｍ］のｎ－１次の係数が１の場合には
［ｘ＾（ｍ＋１）］＝ｘ・［ｘ＾ｍ］＋ｆ（ｘ）－ｘ＾ｎとなり
次のベクトルが今のベクトルだけから除算回路及び加算回路無しに単なる排他的論理和回路で実現できます（もちろんレジスタとａｎｄ回路もいります）