■剰余系と整数生成定規(その13)
pが素数で,p^m個の元をもつ有限体は,コンピュータや通信,暗号化などに対してとくに重要である.
m=4→GF(2^4)は16個の要素
0000,1000,0100,1100,0010,・・・,1111
をもつ(0〜15までの2進数列で,左が最下位ビットとなるように書かれている).
加算と減算はビット毎に2を法として定義される(繰り上げがないので2進の加算とは一致しない).
1100+1111=0011
乗算は,
[1]各ベクトルはm−1次までの2^4個の多項式と対応する.
1100→x^0+x^1+0+0=1+x
0101→0+x^1+0+x^3=x+x^3
[2]与えられた次数mのGF(2)上の既約多項式,たとえば,p=2,m=4の場合は
π(x)=1+x+x^4
π(x)=1+x^3+x^4
π(x)=1+x+x^2x^3+x^4
を法とする多項式の乗算の余りとして定義される.
[3]π(x)=1+x+x^4の場合は,x^4を1+xで置き換えることと同値である.
1101・1001=(1+x+x^3)(1+x^3)
=1+x+x^4+x^6
=1+x+(1+x)+x^2(1+x),係数は2を法として1+1=0より
=x^2+x^3=0011
===================================