位数２の有限体 ( GF(2) ) での1変数多項式の計算 (その1)
元が０と１しかないＧＦ（２）での計算について
ＧＦ（２）での1変数の多項式を考えたとき
係数は０か１なので項は必ずx^3とかx^2とかで3*x^3とか5*x^2とかはない。
定数項は1しかない。
例えば
x^5+x^3+x+1 と
x^5+x^2+x+1 をまじめに足してみると
(x^5+x^3+x+1)+(x^5+x^2+x+1)=(1*x^5+1*x^5)+x^3+x^2+(1*x+1*x)+1+1
=(1+1)*x^5+x^3+x^2+(1+1)*x+(1+1)
=0*x^5+x^3+x^2+0*x+0
=x^3+x^2
足し算すると2個づつあるx^5とxと1が消える。
なんで1+1が０になるかというと1+1=2
2は2で割ったときの余りが０だから
1+1=0なのである。
CRCの計算では、多項式÷多項式をするわけですが、そのとき多項式どうしの引き算
がでてきます。
ですが、次の様にGF(2)における全部の足し算引き算を考えると
1+1=1-1=0
1+0=1-0=1
0+1=0-1=1
0+0=0-0=0
となるので、足し算と引き算が同じになります。
0-1は-1だけどGF(2)の元は0か1なので0か1になるまで次々、2をたしてやる。-1に2をたすと1になって終了。0-1=1となる
-3になった場合でも、0か1になるまで2をたしてやる。
-3に2をたすと-1、0か1にならないので、また2を足す。
すると1になって終了。-3=1となる。
GF(2)では-3は1となる。
多項式の割り算は
x^2+1
＿＿＿＿＿＿＿＿＿＿＿＿
x^3+x+1 ｜ x^5
x^5+x^3+x^2
_______________________
x^3+ x^2
x^3 + x +1
________________________
x^2 + x + 1
のようになって、結果を書くと
x^5 ÷ (x^3+x+1) = x^2+1 余り x^2 + x + 1
となる。
