プロが教えるわが家の防犯対策術!

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

A 回答 (7件)

多分最終版



生成多項式:
Kを体としxを変数としnを自然数としf(x)を「Kの元を係数とするn次多項式」としNをnより大きい自然数としπを「Kの元を係数とする次数がN未満の多項式のうちf(x)で割り切れる多項式の集合」としたときf(x)をπの生成多項式という

既約多項式:
Kを体としxを変数としnを自然数としf(x)を「Kの元を係数とするn次多項式」としたときf(x)=0の根がKに含まれないときf(x)を既約多項式という

原始多項式:
qを自然数としKを「q個の元からなる体」としxを変数としnを自然数としf(x)を「Kの元を係数とするn次多項式」とし自然数mに対して「x^mをf(x)で割ったときの余りの多項式」を[x^m]としたとき
[x^0],[x^1],[x^2],・・・,[x^(q^n-2)]
がすべて異なるときf(x)を原始多項式という

疑似乱数:
qを自然数としKを「q個の元からなる体」としxを変数としnを自然数としf(x)を「Kの元を係数とするn次原始多項式」とし自然数mに対して「x^mをf(x)で割ったときの余りの多項式」を[x^m]とし自然数mに対して「[x^m]の係数を最低次からn個並べてできたベクトル」をv([x^m])としたとき無限のベクトル列
v([x^0]),v([x^1]),v([x^2]),・・・
を疑似乱数という

Kを最も小さい体{0,1}としn=4としたとき
x^4+x+1は既約多項式であり原始多項式だが
x^4+x^3+x^2+x+1は既約多項式であるが原始多項式ではない
両方ともxに0,1いずれを代入しても0でなくK内に根を持たないから両方とも既約多項式であることは明らか
1,x,x^2,x^3,・・・,x^14を上の式で割ったときの余りがすべて異なるから上の式は原始多項式であることは明らか
x^5を下の式で割ったときの余りが1であり[x^5]=1であるから下の式は原始多項式ではないことが明らか

n次の多項式により生成される疑似乱数はq^n-1個の異なるベクトルをq^n-1の周期で順次発生する
(すなわち0ベクトル意外のすべてのn次元ベクトルを発生する)
n=16,q=2とすれば65535のベクトルを65535の周期で順次発生することになります

q=2の場合には疑似乱数発生装置が簡単な論理回路で構成できます
[x^m]のn-1次の係数が0の場合には
[x^(m+1)]=x・[x^m]となり
[x^m]のn-1次の係数が1の場合には
[x^(m+1)]=(x・[x^m]-x^n)+(f(x)-x^n)となり
次のベクトルが今のベクトルだけから除算回路及び加算回路無しに単なる排他的論理和ゲートで実現できます(もちろんnビットレジスタとandゲートも必要です)
注意:q=2の場合1+1=0,1+0=1,0+1=1,0+0=0であり+は排他的論理和
    • good
    • 2

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



生成多項式:
Kを体としxを変数としnを自然数としf(x)を「Kの元を係数とするn次多項式」としNをnより大きい自然数としπを「Kの元を係数とする次数がN未満の多項式のうちf(x)で割り切れる多項式の集合」としたときf(x)をπの生成多項式という

既約多項式:
Kを体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式としたときf(x)=0の根がKに含まれないときf(x)を既約多項式という

原始多項式:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]としたとき
[x^0],[x^1],[x^2],・・・,[x^(q^n-2)]
がすべて異なるときf(x)を原始多項式という

疑似乱数:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次原始多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]とし自然数mに対して[x^m]の係数を最低次からn個並べてできたベクトルをv([x^m])としたとき無限のベクトル列
v([x^0]),v([x^1]),v([x^2]),・・・
を疑似乱数という

Kを最も小さい体{0,1}としn=4としたとき
x^4+x+1は既約多項式であり原始多項式だが
x^4+x^3+x^2+x+1は既約多項式であるが原始多項式ではない
両方とも0,1いずれを代入しても1でありK内に根を持たないから両方とも既約多項式であることは明らか
x^5を下の式で割ったときの余りが1であるから下の式は原始多項式ではないことが明らか

n次の多項式により生成される疑似乱数はq^n-1個の異なるベクトルをq^n-1の周期で順次発生する
n=16,q=2とすれば65535のベクトルを65535の周期で順次発生することになります すごいですね!

q=2の場合には発生装置が簡単な論理回路で構成できます
[x^m]のn-1次の係数が0の場合には
[x^(m+1)]=x・[x^m]となり
[x^m]のn-1次の係数が1の場合には
[x^(m+1)]=x・[x^m]+f(x)-x^nとなり
次のベクトルが今のベクトルだけから除算回路及び加算回路無しに単なる排他的論理和回路で実現できます(もちろんレジスタとand回路もいります)
    • good
    • 0

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



既約多項式:
Kを体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式としたときf(x)=0の根がKに含まれないときf(x)を既約多項式という

生成多項式:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]としたとき
[x^0],[x^1],[x^2],・・・,[x^(q^n-2)]
がすべて異なるときf(x)を生成多項式という

疑似乱数:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次生成多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]とし自然数mに対して[x^m]の係数を最低次からn個並べてできたベクトルをv([x^m])としたとき無限のベクトル列
v([x^0]),v([x^1]),v([x^2]),・・・
を疑似乱数という

Kを最も小さい体{0,1}としn=4としたとき
x^4+x+1は既約多項式であり生成多項式だが
x^4+x^3+x^2+x+1は既約多項式であるが生成多項式ではない
両方とも0,1いずれを代入しても1でありK内に根を持たないから両方とも既約多項式であることは明らか
x^5を下の式で割ったときの余りが1であるから下の式は生成多項式ではないことが明らか

n次の多項式により生成される疑似乱数はq^n-1個の異なるベクトルをq^n-1の周期で順次発生する
n=16,q=2とすれば65535のベクトルを65535の周期で順次発生することになります すごいですね!

q=2の場合には発生装置が簡単な論理回路で構成できます
[x^m]のn-1次の係数が0の場合には
[x^(m+1)]=x・[x^m]となり
[x^m]のn-1次の係数が1の場合には
[x^(m+1)]=x・[x^m]+f(x)-x^nとなり
次のベクトルが今のベクトルだけから除算回路無しに単なる排他的論理和回路で実現できます(もちろんレジスタとand回路もいります)
    • good
    • 0

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



既約多項式:
Kを体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式としたときf(x)=0の根がKに含まれないときf(x)を既約多項式という

生成多項式:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]としたとき
[x^0],[x^1],[x^2],・・・,[x^(q^n-2)]
がすべて異なるときf(x)を生成多項式という

疑似乱数:
qを自然数としKをq個の元からなる体としxを変数としnを自然数としf(x)をKの元を係数とするn次生成多項式とし自然数mに対してx^mをf(x)で割ったときの余りの多項式を[x^m]とし自然数mに対してcの係数を最低次からn個並べてできたベクトルをv([x^m])としたとき無限のベクトル列
v([x^0]),v([x^1]),v([x^2]),・・・
を疑似乱数という

Kを最も小さい体{0,1}としn=4としたとき
x^4+x+1は既約多項式であり生成多項式だが
x^4+x^3+x^2+x+1は既約多項式であるが生成多項式ではない
両方とも0,1いずれを代入しても1でありK内に根を持たないから両方とも既約多項式であることは明らか
x^5を下の式で割ったときの余りが1であるから下の式は生成多項式ではないことが明らか

n次の多項式により生成される疑似乱数はq^n-1個の異なるベクトルをq^n-1の周期で順次発生する
n=16,q=2とすれば65535のベクトルを65535の周期で順次発生することになります すごいですね!

q=2の場合には発生装置が簡単な論理回路で構成できます
[x^m]のn-1次の係数が0の場合には
[x^(m+1)]=x・[x^m]となり
[x^m]のn-1次の係数が1の場合には
[x^(m+1)]=x・[x^m]+f(x)-x^nとなり
次のベクトルが今のベクトルだけから除算回路無しに単なる加算回路で実現できます
    • good
    • 0

既約多項式とは「前記多項式の係数を表現する体」上の根を持たない多項式


生成多項式とは原始元を根に持つ多項式
生成多項式は既約多項式ですが
既約多項式は生成多項式とは限らないのです
その意味で生成多項式は既約多項式のちゃんぴょんです
疑似乱数は生成多項式を使ってレジスタと加算器で作ることができます
係数の体を{0,1}とすると生成多項式の次数をn-1とすれば2**n-1のパターンを発生させることができます
既約多項式ではパターンがもっと少なくなります
嵩は知っていますがkasami係数は知りません
    • good
    • 0

多項式環:


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です。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/01/23 19:13

代数学の体とか有限体とか、符号理論とかをご存じでしょうか?


期末試験対策かもしれませんね。

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

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

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

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

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

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

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

Kasami係数というのも知りませんが、嵩(かさみ)先生というのは
日本の符号理論の第一人者の一人ですので、その関連でしょうか。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/01/23 19:09

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!