■剰余系と整数生成定規(その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

===================================