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

このQ&Aに関連する最新のQ&A

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
    • 0

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



生成多項式:
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に関連する人気のQ&A

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

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q「既約な分数」というのは分かるのですが、「既約な多項式」とはどういうも

「既約な分数」というのは分かるのですが、「既約な多項式」とはどういうもののことなんでしょうか?

Aベストアンサー

惜しい。
多項式が因数分解済みの形で表記してあることを
「既約」というのではありません。
その多項式自体が因数分解不能であることを
「既約」というのです。

例えば、同じ式を
x↑2 - 1 と書いても、(x + 1)(x - 1)と書いても、
この式が有理係数の範囲で2つの一次因子の積に
分解可能であることには、変わりがありません。
x + 1 と x - 1 は、どちらも既約ですが、
(x + 1)(x - 1) は、可約なのです。

x↑2 + 1 であれば、実際係数の範囲では、
これ以上分解することができません。
この状況を、「x↑2 + 1 は、実数上既約だ」
といいます。

尚、因数分解できる/できないの話ですから、
本来は、係数の範囲を明示する必要があります。
文脈上、誤解の余地がなければ、
省略しても構いませんが。

そういった訳で、与えられた多項式が
既約か可約かを判定することならできますが、
「既約な多項式にする」ことなど不可能です。

Q既約多項式の証明

p:素数
Zp=Z/(p)とする.
多項式f(x)=a0+a1x+・・adx^d∈Z[x]に対して、
f ̄(x)=a0 ̄+a1 ̄x+・・ad ̄x^d∈Zp[x]として、(a ̄∈Zpは整数aの剰余項)
最高次の項の係数がpで割れない原始多項式f(x)∈Z[x]について、f ̄(x)がZp[x]の既約元であれば、f(x)はZ[x]の既約元である
ということを示したいのですが、f(x)が既約元でなくf=ghとおいて示そうとしてるのですが、ごちゃごちゃになっていまいちできません。どのような解法が適切でしょうか。

Aベストアンサー

方針は良いと思います。f ̄が既約としてあるのでg ̄かh ̄のどちらかが1でたとえばh ̄を1としましょう。そうするともとのhは定数項以外すべてpの倍数を係数に持つのでfの最高次係数はpの倍数、これはfの仮定と矛盾です。

Q有理数体上既約多項式x^3+ax+bの最小分解体

が有理数体の3次のガロア拡大体になる例を教えてください。
6次ではなく3次の拡大体になる場合の有理数a,bの値例を教えてください。

Aベストアンサー

こんにちわ。

カルダノの方法(公式)を使ってみましょう。
機械的に処理できます。



背景知識としては与式の最小分解体Kとして
f(x)が体F上での既約だとするとF⊂F(√D)⊂Kであり
拡大次数[K:F(√D)]=3 また √D∈F⇔[K:F]=3
これを使います。
このDは判別式です。3つの解をs,t,uとすると
D=(s-t)^2(s-u)^2(t-u)^2=-4a^3-27b^2 これですね。



凄く凄く単純化すると、判別式Dが平方数ならば拡大次数は3になるわけです。色々といじって遊んでみてください。

例えばx^3-3x+1は拡大次数3ですが、x^3+3x+1ならばD<0より次数は6ですね。

Q既約多項式の問題

もし関数f(x)がf(x^2)の因数なら多項式f(x)はfspであると呼びます。また、fspであるf(x)の因数が、fspである低次の関数によって表すことができない時、f(x)をfsp既約関数と呼びます。たとえば、一次のfsp既約関数は、mxとm(x-1)だけです(m は任意のゼロではない実数の定数)。二次の場合、fsp既約関数はx^2+x+1だけです。

(1)3次や4次のfsp既約関数は存在するでしょうか?そういった関数の中で、整数のみを係数とするようなものはあるでしょうか?
(2)fspの関数や、fsp既約関数の性質についてなにか一般化できるでしょうか?

Aベストアンサー

4次の fsp既約関数は簡単に見付かる. x^2+x+1 がなぜ (2次の) fsp既約関数なのかを考えれば難しくないかも.

3次は... 実係数だと存在しないような気がする....

と, とりあえず簡単な (1) だけ.

QM系列の生成多項式と原始多項式について

生成多項式や原始多項式に関する様々な投稿を見ましたが、
いまいち知りたいことがわからなかったので質問いたします。

周期 2^n - 1 のM系列を生成するには、{0,1}を体とする
n次の原始多項式を生成多項式として用いるということまでは
わかったのですが、このn次の原始多項式の求め方について、
いまいち理解できません。

例えば、周期 2^4 - 1 = 15のM系列を生成するには原始多項式

          x^4 + x^1 + 1 ー (1)

を用いるということですが、

            x^4 + x^2 + 1 ー (2)

ではM系列を生成できませんでした。
この2式の違いを理解していないことが原始多項式の求め方を
理解できない原因だと思うのですが、どなたかお詳しい方がいましたら、
ご教授お願いいたします。

Aベストアンサー

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼び名があるが、ここではF2と呼びます)を考えていますよね。

x^4 + x^2 + 1 でF2上の(つまり、係数が0と1からなる)多項式を割った「余り」を考えるとき、全ての多項式は、余りは3次以下の(係数が0と1からなる)式になりますよね。

係数が0と1であることから、ax^3 + bx^2 + cx + d たちは、全部で 2^4 = 16 個あるわけです。

いま、4次の原始多項式とは、xが、0を除く15個の余りを全て生成するような多項式を言います。

具体的に言うと、x , x^2 , x^3 , ・・ , x^15 を夫々割った余りがすべて異なり、0以外の全ての3次式が出てくるとき、原始多項式と言います。

ということは、もし途中で(余りとして)1がでたら、次から x , x^2 ・・と最初からの繰り返しになるので、駄目です。
よって x^15 の余りが1であり、それ以前に余り1が出てはいけません。

実は、この逆が言えて、
x , x^2 , x^3 , ・・ , x^14 の余りがすべて1でないとき(つまり x^15 ではじめて1になるとき)、(4次の)原始多項式である ・・・★

ことが言えます。

なので、(もっと良いテクニックは色々あるでしょうが)、★を満たすかどうかを、まじめに計算すれば分かります。

いま x^4 + x^2 + 1 についてやってみると、
x^4 + x^2 + 1 で割った余りは、x^4 + x^2 + 1 = 0 として、x^4 = x^2 + 1 (注:いまF2(2で割った余りの世界)上で考えているから、-1=1) を代入して次数を下げてゆけば求まりますよね。

すると、
x
x^2
x^3
x^4 = x^2 + 1
x^5 = x(x^2 + 1) = x^3 + x
x^6 = x(x^3 + x) = x^4 + x^2 = x^2 + 1 + x^2 = 1
( 2 = 0 より、2x^2 = 0 )
となり、6乗で1になってしまうので、 x^4 + x^2 + 1 は原始多項式でないと分かりますネ。

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼...続きを読む


人気Q&Aランキング

おすすめ情報