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

tecchan22 · ベストアンサー

＃１さんミスしてますので修正を。

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プログラムで生成しようとして、元の原始多項式の
設定のところでつまずいていたので質問させてもらいました。
当面は教えていただいた方法でアルゴリズムを書いてみるつもりです。

わかりやすく御回答していただき、ありがとうございました。

回答No.1

Tacosan

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

お礼

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