@http://blog.goo.ne.jp/bonsai-chat/e/f7d912562aedc291be2a730692b7866f
=?H13%0:多項式の計算
/作成中(無視してください)
?H13%0:多項式の計算
%01:まえがき
・[%1]は実係数多項式の計算(中学・高校の復習)
・[%2]は「GF(22m)」上の多項式の計算
・[%3]は[%2]の補足
%02:目次{}
%03:補遺
%031:?H12%0:複素数の計算
http://blog.goo.ne.jp/bonsai-chat/e/84936cb77def8daaad96e74f1d9e461d
%032:有限体
http://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E4%BD%93
%033:体の拡大
http://ja.wikipedia.org/wiki/%E4%BD%93%E3%81%AE%E6%8B%A1%E5%A4%A7
%034:剰余類
http://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E9%A1%9E
%035:M系列
http://ja.wikipedia.org/wiki/M%E7%B3%BB%E5%88%9
%036:円分多項式 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%86%86%E5%88%86%E5%A4%9A%E9%A0%85%E5%BC%8F
037:modulo2の論理演算回路 - 信州大学
http://laputa.cs.shinshu-u.ac.jp/~yizawa/logic2/chap7/
038:Excel・エクセルの使い方|初心者の基本からデキる応用技まで!
http://www.becoolusers.com/excel/
%04:訂正{}
%05:質問
%051:原始多項式の求め方 - 数学 締切済 | 教えて!goo
http://oshiete.goo.ne.jp/qa/5166940.html
%052:M系列の生成多項式と原始多項式について - 数学 解決済 | 教えて!goo
http://oshiete.goo.ne.jp/qa/3606254.html
%06:回答
%061:原始多項式とその積について | 高校数学の美しい物語
http://mathtrain.jp/primpolynomial
%062:原始多項式がよくわからない - 備忘録
http://d.hatena.ne.jp/atk-x11/20090116/1232119885
%063:この記事の[%26]:原始多項式
http://blog.goo.ne.jp/bonsai-chat/e/f7d912562aedc291be2a730692b7866f
・除算「1/G(x)」を続行したときの周期系列は伝達関数が「1/G(z-1)」であるディジタルフィルタのインパルス応答と等しくなります.
%1:多項式の四則演算
変数「x」の実係数多項式について考える(中学・高校での計算と同じ)
%11:加算
・e.g.「(x+2)+(2x+3)=3x+5」
%12:減算
・e.g.「(x+2)-(2x+3)=-x-1」
%13:乗算
・e.g.「(x+2)*(2x+3)=2x2+7x+6」
%14:除算
・e.g.「(x+2)/(2x+3)=(1/2)*(2x+3)+(1/2)」
・N.B.「P(x)=Q(x)*G(x)+R(x)」(「R(x)」は「G(x)」より低次の多項式)である「R(x)」を除算「P(x)/G(x)」の剰余という.
1/2 「 (x+2)/(2x+3)=Q(x)*(2x+3)+R(x)」
2x+3)x+2 (「2x+3」は1次の多項式だから「R(x)」は定数 )
x+3/2
1/2
%2:{0,1,-1}上の多項式
%21:有限体GF(p)
素数「p」より小さい負でない整数の集合を「K」とし,「K」上の四則演算を「p」を法とする加法および乗法で定めると,「K」は有限体になる.この「K」を「GF(p)」という.([%032])
%22:「GF(p)」上の多項式への変換
整係数の「x」を変数とする多項式に対して[%1]のような通常の四則演算を行い,計算で得られた多項式の各項の係数をこれと合同な「GF(p)」の元で置換することを,「GF(p)」上の多項式への変換という.
・e.g.[%13]の「2x2+7x+6」を「GF(5)」上の多項式に変換すると「2x2+2x+1」.
考え易いように,集合{0,1,-1}の元を係数とする変数「x」の多項式「P(x)」を「0」「-1」,「1」,「-1」を「0」「+」「-」で表わした係数ベクトル『□』で表現する.
・e.g.「x4-1」は『+000-』
%24:「xn-1」の因数分解
「x」を複素数と考えると多項式も「数」なので,「P(x)」を他の多項式の積で表現することを因数分解という(定数(0次の式)は除外).
・因数分解できない多項式を既約多項式という.
%241:「n=22」のとき「x4-1=(x-1)(x+1)(x2+1)」
『+-』 『+0-』 .
×『++』 ×『+0+』 .
+- +0- .
+- +0- .
『+0-』 『+000-』 .
%242:「n=23」のとき「(x-1)(x+1)(x2+1)(x4+1)」
%243:「n=23-1」のとき「(x-1)(x3+x+1)(x3+x2+1)」
『++0+』 『+++++++』
× 『+0++』 × 『+-』
++0+ -------
++0+ +++++++ .
++0+ 『+000000-』
『+++++++』
%25:円周等分多項式
方程式「xn-1=0」(「x」は複素数)の根「ei2kπ/n」(0`≦k`<n)は複素数平面上の単位円を「n」等分する.
%251:「x4-1=(x-i0)(x-i1)x-(i2)(x-i3)」.
%26:原始多項式
「P(x)」が「G(x)」(「m」次とする)で割り切れないときは「P(x)/G(x)」の剰余(「m-1」次以下の式)は有限個だから除算の途中で同じ多項式が現れる.とくに剰余に「0」以外のすべての多項式が現れるとき,「G(x)」を原始多項式という[%035].
・e.g.[%243]の「(x3+x+1)」,「(x3+x2+1)」
・「G(x)=0」ならば「xn-1=0」([%25])
%261:「P(x)=x10」,「G(x)=x2+1」とし,除算「P(x)/G(x)」を計算すると,
「x10/(x2+1)=x8-x6+x4-x2+…」(「P(x)=x10-x4」ならば割り切れる)
%262:「P(x)=x10」,「G(x)=x3+x+1」とし,除算「P(x)/G(x)」を計算する場合,ぼんさいノート「[sys.pdf].[#44]の
のような回路の動作は次の漸化式で調べることができる(0`≦k`<23 -1).
「w0(0)=1」,「w0(0)=0」,「w0(0)=0」
「w0(k+1)=w1(k)」,「w1(k+1)=w2(k)」,「w2(k+1)=w0(k)+w1(k)」
・時刻「k」の剰余は 「(w0(k),w1(k),w2(k))」 (動作は[%037]参照)
k (w0(k), w1(k), w2(k))
0 ( 1 , 0 , 0 ) 4
1 ( 0 , 0 , 1 ) 1
2 ( 0 , 1 , 0 ) 2
3 ( 1 , 0 , 1 ) 5
4 ( 0 , 1 , 1 ) 3
5 ( 1 , 1 , 1 ) 7
6 ( 1 , 1 , 0 ) 6 /*1+1=0*/
7 ( 1 , 0 , 0 ) 4 /*1+1=0.初期値に戻っている*/
%2621:MS Excelによる計算
[%262]のM系列はMS Excelで容易に計算できる(「C2」はGF(2)上の加算).
1: 1 0 0 1(1行目:初期値)
2: 0 0 1 0(2行目:下記の式をコピー)
3: 0 1 0 1(3行目:2行目を下方向にコピー)
4: 1 0 1 1
5: 0 1 1 1
6: 1 1 1 0(/* 1+1=0 */)
7: 1 1 0 0(/* 1+1=0 */)
8: 1 0 0 1(8行目:終了)
「 1」,「 0」,「 0」,「 1」
「A2=B1」,「B2=C1」,「C2=IF(D1>1,D1-2, D1)」,「D2=A2+B2」
%3:{0,1,2}上の多項式
簡単のため自然数を係数とする多項式を考え,四則演算を行った多項式の各項の係数を
3を法とする剰余で置換します.(がロア拡大体GF(3m)上の多項式の計算に相当)
・i.e.「0+k=k」,「0*k=0」,「2+1=0」,「2*2=1」
aa