M系列の係数を教えてください

質問

みなさんこんにちは、

32ビットCPUでM系列を発生させるプログラムをつくりたいのですが、係数がわかりません。

32ビット unsigned char １個を記憶領域として使いたいのですが、その場合の最大次元の係数を教えてください。

どうぞよろしくお願いします。

回答No.7

keyguy · ベストアンサー

またコピーで間違いが

(1)
既約多項式どうかの判定はK={0,1}とし以下のようにする
{x^32+x・f(x)+1|f(x)は30次以下の奇数項K係数多項式}
の各元について
{g(x)|g(x)は2次以上16次以下のK係数既約多項式}
の元すべてについて割れないものを既約多項式とする

(2)
1で求めた規約多項式h(x)が原始多項式かどうかの判定を以下のようにする((2^32-1)/3=1431655765に注意)
x,x^2,x^3,x^4,・・・,x^1431655765
をh(x)で割ったあまりを
i[1](x),i[2](x),i[3](x),・・・,i[1431655765](x)
とすると
i[n](x)が30次以下の場合には
i[n+1](x)=x・i[n](x)であり
i[n](x)が31次の場合には
i[n+1](x)=x・i[n](x)+h(x)である
(よってi[n+1](x)は31次以下である)
このようにして1431655765番目まで求めその途中でi[・](x)が1になれば原始多項式でないので止めi[・](x)が最後まで1でなければh(x)は原始多項式である

以上は１つの原始多項式が求まればそこで止めれば良いのでそれほど計算時間はかからないでしょう
項数が少ないものをほしいので項数が少ないものから順に検査すれば良い

回答No.6

keyguy

(1)
既約多項式どうかの判定はK={0,1}とし以下のようにする
{x^32+x・f(x)+1|f(x)は30次以下の奇数項K係数多項式}
の各元について
{g(x)|g(x)は2次以上15次以下のK係数既約多項式}
の元すべてについて割れないものを既約多項式とする

(2)
1で求めた規約多項式h(x)が原始多項式かどうかの判定を以下のようにする((2^32-1)/3=1431655765に注意)
x,x^2,x^3,x^4,・・・,x^1431655765
をh(x)で割ったあまりを
i[1](x),i[2](x),i[3](x),・・・,i[1431655765](x)
とすると
i[n](x)が30次以下の場合には
i[n+1](x)=x・i[n](x)であり
i[n](x)が31次の場合には
i[n+1](x)=x・i[n](x)+h(x)である
(よってi[n+1](x)は31次以下である)
このようにして1431655765番目まで求めその途中でi[・](x)が1になれば原始多項式でないので止めi[・](x)が最後まで1でなければh(x)は原始多項式である

以上は１つの原始多項式が求まればそこで止めれば良いのでそれほど計算時間はかからないでしょう
項数が少ないものをほしいので項数が少ないものから順に検査すれば良い

回答No.5

keyguy

コピーでやったので一部間違い

(1)
既約多項式どうかの判定はK={0,1}とし以下のようにする
{x^32+x・f(x)+1|f(x)は30次以下の奇数項K係数多項式}
の各元について
{x・g(x)+1|g(x)は15次以下の偶数項K係数多項式}
の元すべてについて割れないものを既約多項式とする

(2)
1で求めた規約多項式h(x)が原始多項式かどうかの判定を以下のようにする((2^32-1)/3=1431655765に注意)
x,x^2,x^3,x^4,・・・,x^1431655765
をh(x)で割ったあまりを
i[1](x),i[2](x),i[3](x),・・・,i[1431655765](x)
とすると
i[n](x)が30次以下の場合には
i[n+1](x)=x・i[n](x)であり
i[n](x)が31次の場合には
i[n+1](x)=x・i[n](x)+h(x)である
(よってi[n+1](x)は31次以下である)
このようにして1431655765番目まで求めその途中でi[・](x)が1になれば原始多項式でないので止めi[・](x)が最後まで1でなければh(x)は原始多項式である

以上は１つの原始多項式が求まればそこで止めれば良いのでそれほど計算時間はかからないでしょう
項数が少ないものをほしいので項数が少ないものから順に検査すれば良い

回答No.4

keyguy

(1)
既約多項式どうかの判定はK={0,1}とし以下のようにする
F={x^32+x・g(x)+1|g(x)は30次以下の奇数項K係数多項式}
の各元について
H={x^16+x・i(x)+1|i(x)は14次以下の奇数項K係数多項式}
の元すべてについて割れないものを既約多項式とする

(2)
1で求めた規約多項式h(x)が原始多項式かどうかの判定を以下のようにする
((2^32-1)/3=1431655765に注意)
x,x^2,x^3,x^4,・・・,x^1431655765
をh(x)で割ったあまりがすべて1でなければh(x)は原始多項式である
n番目が31次でありj(x)だとするとn+1番目は
j(x)・x+h(x)
(31次以下)となる
このようにして1431655765番目まで求めその途中で1になれば原始多項式でないので止める

以上は１つの原始多項式が求まればそこで止めれば良いのでそれほど計算時間はかからないでしょう

回答No.3

keyguy

既約でない→既約の間違い

(1)
x^4+x+1
x^4+x^2+1
x^4+x^3+1
x^4+x^2+x+1
x^4+x^3+x+1
x^4+x^3+x^2+1
x^4+x^3+x^2+x+1
が既約かどうかを順に確かめる
(x+1)
(x^2+x+1)　
で割れるかどうかを順に確かめれば良い
(2次以上は3項以上係数が0でないはず)
(項数が偶数の場合はx+1で割れるから項数が奇数の場合だけ検査することにすればx+1を割れるかどうか確かめなくても良い)

(2)
x^4+x+1が既約であることが判明したので原始かどうか確かめる
2^4-1=15=3×5
だからx^5をx^4+x+1で割ったあまりが1出ないならば原始
そのまま割ってもいいが次数が多い時のためにNo.1の方法を取る
x^1,x^2,x^3,x^4=x+1,x・(x+1)=x^2+x
よって5番目が1でないから
x^4+x+1が原始多項式で有ることが分かる
5番目に達する前にに1になればそこで止めれば良いから計算数はもっと減る)

回答No.2

keyguy

多少数について2倍ほど違うところがあったけれども考えからだけ受け取ってもらえれば幸いです
イメージをつかむために4次の場合を考えよう

(1)
x^4+x+1
x^4+x^2+1
x^4+x^3+1
x^4+x^2+x+1
x^4+x^3+x+1
x^4+x^3+x^2+1
x^4+x^3+x^2+x+1
が既約かどうかを順に確かめる
(x+1)
(x^2+x+1)　
で割れるかどうかを順に確かめれば良い
(2次以上は3項以上係数が0でないはず)

(2)
x^4+x+1が既約でないことが判明したので原始かどうか確かめる
2^4-1=15=3×5
だからx^5をx^4+x+1で割ったあまりが1出ないならば原始
そのまま割ってもいいが次数が多い時のためにNo.1の方法を取る
x^1,x^2,x^3,x^4=x+1,x・(x+1)=x^2+x
よって5番目が1でないから
x^4+x+1が原始多項式で有ることが分かる

回答No.1

keyguy

周期2^32-1のM系列を求めたいのですか?

{0,1}からなる体を係数とする32次原始多項式を求めればいいでしょう

(1)
f(x)=x^32+・・・+1
が既約多項式になっているかどうかを各「・・・」について総当りで調べてみる
といっても割れるかどうかを確かめるのは
1つの多項式当たり
x+1
から
x^16+x^15+x^14+・・・+x^5+x^4+x^3+x^2+x^2+x+1
までだから3万通りあまりなのでそれほど時間がかからない
(最上位係数と最下位係数が1だから2^14×2=2^15足らず)

(2)
f(x)が既約多項式で有った場合に
x^((2^32-1)/3)=x^1431655765をf(x)でわったあまりが1にならなければ
f(x)が原始多項式である
実際には
x,x^2,x^3,・・・
においてx^32の項が出てきたら既約多項式で同一次数の係数同士EOR算し常に31次以下の多項式であるようにし
その1431655765番目が1でならないならばf(x)が原始多項式である