• ベストアンサー
  • すぐに回答を！

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

生成多項式や原始多項式に関する様々な投稿を見ましたが、 いまいち知りたいことがわからなかったので質問いたします。 周期 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系列を生成できませんでした。 この２式の違いを理解していないことが原始多項式の求め方を 理解できない原因だと思うのですが、どなたかお詳しい方がいましたら、 ご教授お願いいたします。

共感・応援の気持ちを伝えよう！

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.2

＃１さんミスしてますので修正を。 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} だから、そもそも既約でないので、原始多項式にはなりません。 （原始多項式ならば、既約。逆は言えませんが） しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。 いま、数・係数としては、２で割った余りの世界（０と１からなる四則の出来る世界。色んな呼び名があるが、ここではＦ２と呼びます）を考えていますよね。 x^4 + x^2 + 1 でＦ２上の（つまり、係数が０と１からなる）多項式を割った「余り」を考えるとき、全ての多項式は、余りは３次以下の（係数が０と１からなる）式になりますよね。 係数が０と１であることから、ax^3 + bx^2 + cx + d たちは、全部で 2^4 = 16 個あるわけです。 いま、４次の原始多項式とは、ｘが、０を除く１５個の余りを全て生成するような多項式を言います。 具体的に言うと、x , x^2 , x^3 , ・・ , x^15 を夫々割った余りがすべて異なり、０以外の全ての３次式が出てくるとき、原始多項式と言います。 ということは、もし途中で（余りとして）１がでたら、次から x , x^2 ・・と最初からの繰り返しになるので、駄目です。 よって x^15 の余りが１であり、それ以前に余り１が出てはいけません。 実は、この逆が言えて、 x , x^2 , x^3 , ・・ , x^14 の余りがすべて１でないとき（つまり　x^15 ではじめて１になるとき）、（４次の）原始多項式である　・・・★ ことが言えます。 なので、（もっと良いテクニックは色々あるでしょうが）、★を満たすかどうかを、まじめに計算すれば分かります。 いま x^4 + x^2 + 1 についてやってみると、 x^4 + x^2 + 1 で割った余りは、x^4 + x^2 + 1 = 0 として、x^4 = x^2 + 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 ） となり、６乗で１になってしまうので、 x^4 + x^2 + 1 は原始多項式でないと分かりますネ。

共感・感謝の気持ちを伝えよう！

質問者からのお礼

なるほど、{0,1}を体にするとは２で割った余りの世界を 考えているということなのですね。 あと、原始多項式についても理解できました。 実はM系列をCプログラムで生成しようとして、元の原始多項式の 設定のところでつまずいていたので質問させてもらいました。 当面は教えていただいた方法でアルゴリズムを書いてみるつもりです。 わかりやすく御回答していただき、ありがとうございました。

その他の回答 (1)

  • 回答No.1
  • Tacosan
  • ベストアンサー率23% (3656/15482)

原始多項式の求め方は知りませんが, (2) は x^4 + x^2 + 1 = (x^2 + x + 1)^2 ですから, 原始多項式ではありません. 「原始多項式」というのは, 「より低次の多項式では割切れない多項式」のことです.

共感・感謝の気持ちを伝えよう！

質問者からのお礼

なるほど、確かに因数分解できてしまいますね＾＾； ご指摘ありがとうございます。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 原始多項式の求め方

    ９段M系列の生成多項式となる原始多項式の求め方を教えてください。 今のところx^9+x^5+1やx^9+x^4+1が原始多項式であることがネットなどを調べていてわかりましたが、求め方はわかりません。 また、上記の２式が原始多項式であるかどうか判別するようなこともできるのでしょうか？ 数学に関しては素人なので"何を勉強すればわかるか"だけでも教えていただけると助かります。 よろしくお願いします。

  • 超高次の多項式の原始関数を求めたいのですが

    f(x) = (n-x)(n-1-x)(n-2-x).....(n-m-x) n: 大きな自然数(例えば1000000など) m: n>mの大きな自然数(例えば100000など) という多項式 f(x)の原始関数を高速に求めるアルゴリズムを考えて います． f(x)を具体的に展開してから原始関数を求めれば簡単だと思い，上記 の式を展開するプログラムを書いたのですが，組み合わせの計算を する必要が生じて，mの値が大きな時に高速に計算できませんでした． 原始関数を直接導出しようと，いろいろ場合分けして考えてみたので すが挫折しました． アドバイス頂けませんでしょうか？ よろしくお願いします．

  • ＧＦ（５）のガロア体の原始多項式

    多値Ｍ系列について勉強にどうしても必要なため質問です。 ＧＦ（５）の原始多項式はいったいいくつ存在し、具体的にどういった値をもつのでしょうか？ 自分でがんばって計算し 「x^2+x^1+2」 がＧＦ（５）の原始多項式の一つであることがわかったのですが、その他は存在するのでしょうか、、、？ ＧＦ（２＾ｎ）の原始多項式の解説はよく見るのですが、ＧＦ（５）がなくて困っています。

  • 原始多項式の証明

    原始多項式の証明 すみませんこの問題がどうしてもわかりません。だれか教えていただけないでしょうか？ x^4+x+1（この式はFp[x]に含まれる、p=2）はFp上の４次原始多項式であることを示せ。 まず、既約多項式であることを証明して、原始多項式であることを証明するのだと思うのですが・・・ どうかお願いします。

  • 関数、多項式

    n、kを自然数とすると、1^k+2^k+3^k+…+n^kはnの(k+1)次の多項式として表わされるので、それをS(n,k)と書きます。 f(x)が高々k次のxの多項式で、f(0)=0かつ f(m+1)-f(m)=m^(k-1) がm=1,2,3,…,kで成り立つとき、任意の実数xに対してf(x)=S(x-1,k-1) が成り立つような気がするのですが、これはどうやって示せますか？

  • 最長周期系列(M系列？)の生成プログラム(C言語)

    擬似乱数などに使用される最長周期系列をシフトレジスタ数nを入力として生成するプログラムを探しているのですが、どれだけ探しても乱数生成のプログラムはあっても最長周期系列のほうのプログラムが見当たらないのです。 C言語で探しています。 ソースコードも含めてどうかよろしくお願いします。

  • javascriptで素数と原始元を作りたいです

    JavaScriptで素数生成と原始元してますがうまくいきません助けて！！ 乱数(n)を生成 ↓ 乱数（n）を素数判定する（違うなら最初からやり直す） ↓ nを使って 2n+1＝mとする ↓ mを素数判定する（違うなら最初からやり直す） ↓ ボタンを押してテキストボックスに結果を表示 素数m：○○ mに対しての原始元はn：×× とやりたかったのですがうまくいきません。 至急お願いします。

  • x^m　(mはm≦-1を満たす整数)を含む関数f(x)は多項式でない理由について

    インターネット等で調べてみたのですが見当たらないので質問です。 『x^m(mはm≦-1を満たす整数)を含む関数f(x)は多項式でない理由』とこういった項を含む式の『○○式』等といった呼び方（あれば）を教えてください。 また某pediaを参照すると『f(x)=0という多項式f(x)の次数を-∞と定義する。』とあったのですが、次数が+∞の多項式は存在するのでしょうか？ f(x)=sinxはｘで微分しても、第ｎ次導関数において次数が0にならないためsinxは多項式ではない。と説明しているページも見かけたので正直混乱しています。どなたか教えてください。

  • 補間多項式

    「相異なる点、x_0,x_1,・・・・,x_nに対して、任意の実数y_0,y_1,・・・,y_nがある。そのときp_n+1(x_i)=y_i(i=0,1,・・・,n)を満たす高々n+1次の補間多項式p_n+1がただ一つ存在する。」は真か偽を判定する問題です。考えたのですが偽でしょうか？定義は「与えられた関数y=f(x)に対して、相異なる点x_0,・・・,x_n-1（この点を標本点という）について、y_k=f(x_k),k=0,1,・・・,n-1とおく。このとき高々n-1次多項式p(x)としてp(x_k)=y_k,k=0,1,・・・,n-1となるものがある」理由はやはり高々n+1次というところが定義からづれているからです。しかし根拠が示せないので、アドバイスありましたら嬉しいです・・・

  • 代数の既約多項式の問題です。

    代数の既約多項式の問題です。 a_n(x^n)＋a_n-1(x^n-1)～＋a_2(x^2)＋a_1(x)＋a_0=0 （a_0,a_1,・・・a_n∈Q:有理数） が既約とする。この方程式の解がn次未満のQ係数多項式の解とはならない事を示せ。 既約多項式:これ以上約せない多項式 わかる方いましたらよろしくお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する
質問する