生成多項式

質問

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

回答No.7

nuubou

多分最終版

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

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

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

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

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

ｎ次の多項式により生成される疑似乱数はｑ＾ｎ－１個の異なるベクトルをｑ＾ｎ－１の周期で順次発生する
（すなわち０ベクトル意外のすべてのｎ次元ベクトルを発生する）
ｎ＝１６，ｑ＝２とすれば６５５３５のベクトルを６５５３５の周期で順次発生することになります

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

回答No.6

nuubou

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

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

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

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

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

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

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

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

回答No.5

nuubou

またまた馬鹿な間違いをしたので改訂版を送ります

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

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

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

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

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

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

回答No.4

nuubou

不注意の間違いをしていましたのでもう一度送ります

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

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

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

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

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

ｑ＝２の場合には発生装置が簡単な論理回路で構成できます
［ｘ＾ｍ］のｎ－１次の係数が０の場合には
［ｘ＾（ｍ＋１）］＝ｘ・［ｘ＾ｍ］となり
［ｘ＾ｍ］のｎ－１次の係数が１の場合には
［ｘ＾（ｍ＋１）］＝ｘ・［ｘ＾ｍ］＋ｆ（ｘ）－ｘ＾ｎとなり
次のベクトルが今のベクトルだけから除算回路無しに単なる加算回路で実現できます

回答No.3

nuubou

既約多項式とは「前記多項式の係数を表現する体」上の根を持たない多項式
生成多項式とは原始元を根に持つ多項式
生成多項式は既約多項式ですが
既約多項式は生成多項式とは限らないのです
その意味で生成多項式は既約多項式のちゃんぴょんです
疑似乱数は生成多項式を使ってレジスタと加算器で作ることができます
係数の体を｛０，１｝とすると生成多項式の次数をｎ－１とすれば２＊＊ｎ－１のパターンを発生させることができます
既約多項式ではパターンがもっと少なくなります
嵩は知っていますがｋａｓａｍｉ係数は知りません

回答No.2

stomachman

多項式環：
punchan_jpさんの仰る通り、符号理論では多項式の環（多項式環）の性質を利用します。

多項式は可換環(かかんかん。commutative ring）をなすことはご存知かと思います。つまり
　ある集合Aにおいて、任意の元x,y,z∈Aについて
　●足し算(+)についてAは可換群(group)である。すなわち
・x+y∈A,
・x+y=y+x,
・x+(y+z)=(x+y)+z,
・x+a=yとなるa∈Aが唯一つ存在する。
　●さらにかけ算について、
・(xy)z = x(yz),
・x(y+z) = xy+xz,
・(x+y)z = xz+yz,
　である。このようなAを環と言い、さらに、環であってしかも
・xy = yx
　である場合に、Aを可換環と言うのでした。
　「既約多項式」というのは、他の元で割り切れないもののことです。多項式環における「素数」のようなものですね。
　さて、多項式は群でもある。「生成多項式」とは、この群における生成元(generator)のことです。一般に群Gのある部分集合Sがあって、Sの要素s[1],s[2],....を使ってp=n[1]s[1]+n[2]s[2]+.....　　（n1,n2,...は整数）という形に表せる要素だけを集めた集合をQとするとき、Qを「Sから生成された部分群」と言い、Sの要素を「Qの生成元」と言います。
特に、旨くSを選んで Q=Gになるようにできた場合、Sの要素を「Gの生成元」と言います。
　たとえば符号理論では、ありとあらゆる多項式を使うわけではなく、その部分集合がなす群を利用しますので、生成元（生成多項式）を組み合わせて部分群を構成するわけです。

疑似乱数：
　「乱数」は数列の要素の間に全く関連がない、そういう数列です。本当に乱数列を作り出したかったら、自然のランダム現象を観測して使うしかありません。たとえば抵抗器の中の熱雑音をサンプリングするとか。
　これじゃ大変ですし、また同じ乱数列で計算をやり直したい、なんて事になると、全部記録しておかないといけない訳です。それで、アルゴリズムで乱数列を作り出す。もちろん厳密な意味で「数列の要素の間に全く関連がない」という訳には行きませんが、統計的な解析をしても本物の乱数とほとんど見分けがつかないような数列を作る。これが「疑似乱数」です。詳しく研究されており、近年随分進歩しました。
　奥村晴彦「C言語によるアルゴリズム事典」（技術評論社）に具体例が載っていて便利です。

KASAMI係数：
　stomachmanが知っているKASAMI係数に最も近い言葉はsashimi-teishokuです。

お礼

とても役に立ちました！ありがとうございました。これからもよく聞くと思うのでよろしくお願いします。

回答No.1

punchan_jp

代数学の体とか有限体とか、符号理論とかをご存じでしょうか？
期末試験対策かもしれませんね。

なにをどこまで知った上でのご質問かによるのですが、生成多項式
と既約多項式についてだけ…

多項式と多項式を掛けると、多項式を得られるのはわかりますよね？
逆に、そうして得られた多項式は因数分解してもとの多項式に戻す
ことも可能です。このような因数分解がそれ以上できない多項式を
既約多項式といいます。素数みたいなもんですね。

よくみる数学では、多項式の各項の係数は実数で無限個です。でも、
有限の値集合を考えて、それらの値の間の演算がそれらの間で閉じ
ていて、体をなしていれば（つまり有限体であれば）、そういう有
限個の種類の係数しか許さない多項式というのも考えることができ
ます。このような有限体上の多項式でも乗算や既約といった概念は
有効です。

生成多項式というのは、符号理論の用語です。符号というのは、何
らかのメッセージを有限の種類の記号の列で表すことですが、この
列を符号語と言います。この有限の種類の記号それぞれを多項式の
各項の係数と考えてしまうと、符号語を有限体上の多項式で表すこ
とができるわけです。これを符号多項式といいます。

ところが、長さの決まったある種の符号（巡回符号）を考えると、
その符号に属する符号多項式はすべてその符号の固有の多項式で割
り切れるという性質があります。この固有の多項式のことを生成多
項式といいます。

有限種類の記号の列からなるメッセージから、ある巡回符号の符号
多項式を作るには、そのメッセージを多項式で表してから各項の次
数を一定数増加させたあと、生成多項式で割った余りを引いてやる
だけです。こうしてできた多項式を生成多項式で割っても、もう余
りは出ませんので、符号多項式のできあがりというわけです。

擬似乱数係数というのは知りません。

Kasami係数というのも知りませんが、嵩（かさみ）先生というのは
日本の符号理論の第一人者の一人ですので、その関連でしょうか。

お礼

とても役に立ちました！ありがとうございました。これからもよく聞くと思うので、どうぞよろしくお願いします。