ガロア体補足

ガロア体の簡単な説明　（９９・１２・２７）

琉球大学　情報工学科　和田知久

ガロア体

整数の集合は｛..., -1, 0, 1, 2, ...｝と無限の要素から成り立っているのに対して、
ガロア体とは整数を素数（たとえば５）で除算した余りの集合｛0, 1, 2, 3, 4｝のように
要素が有限で四則演算が閉じている集合である。

例（１）　整数を５で除算した余りの集合｛０，１，２，３，４｝

整数を５で除算した余りの集合｛０，１，２，３，４｝
加算のすべての組み合わせを以下に示す。
全組み合わせに対して、加算の結果は｛０，１，２，３，４｝の要素であり、加算に関して閉じている。
加算の結果の各行、列に｛０，１，２，３，４｝の要素がすべて含まれているので、減算に関しても閉じている。（加算の結果（表の右下の５ｘ５の要素）から好きな数字（水色の数字）を減算した時の結果を表から読み取れる。）

加算	０	１	２	３	４
０	０	１	２	３	４
１	１	２	３	４	０
２	２	３	４	０	１
３	３	４	０	１	２
４	４	０	１	２	３

乗算のすべての組み合わせを以下に示す。
全組み合わせに対して、乗算の結果は｛０，１，２，３，４｝の要素であり、乗算に関して閉じている。
０以外の乗算の結果の各行、列に｛０，１，２，３，４｝の要素がすべて含まれているので、除算に関しても閉じている。（０では当然除算できない）

乗算	０	１	２	３	４
０	０	０	０	０	０
１	０	１	２	３	４
２	０	２	４	１	３
３	０	３	１	４	２
４	０	４	３	２	1

ということで、整数を５で除算した余りの集合｛０，１，２，３，４｝はガロア体です！

例（２）　整数を４で除算した余りの集合｛０，１，２，３｝

整数を４で除算した余りの集合｛０，１，２，３｝
加算のすべての組み合わせを以下に示す。
全組み合わせに対して、加算の結果は｛０，１，２，３｝の要素であり、加算に関して閉じている。
加算の結果の各行、列に｛０，１，２，３｝の要素がすべて含まれているので、減算に関しても閉じている。

加算	０	１	２	３
０	０	１	２	３
１	１	２	３	０
２	２	３	０	１
３	３	０	１	２

乗算のすべての組み合わせを以下に示す。
全組み合わせに対して、乗算の結果は｛０，１，２，３｝の要素であり、乗算に関して閉じている。
０以外の乗算の結果の各行、列に｛０，１，２，３｝の要素がすべて含まれていないので、除算に関して閉じていない。（この表から１÷２、３÷２は計算できない！！！）

乗算	０	１	２	３
０	０	０	０	０
１	０	１	２	３
２	０	２	０	２
３	０	３	２	１

ということで、整数を４で除算した余りの集合｛０，１，２，３｝はガロア体ではない！
除算を素数でやらないとだめです！

ここまでは非常に簡単！

GF(2)

コンピュータやデジタル通信では、通常１と０の２つのシンボルが用いられる。これらに対して法２(mod 2、２で除算した余り）の加算、乗算は以下のようになります。

加算	０	１
０	０	１
１	１	０

すなわち、加算はEXORで、１＋１＝０ですので１＝－１となることに注意してください。

乗算	０	１
０	０	０
１	０	１

すなわち、乗算はANDということになります。
上記表より、減算、除算についても閉じていますので、この２つの元（要素）からなる体を２元体と呼び、GF(2)と表します。

2＾w（２のw乗）の要素(元）をもつ体は2＾wのガロア拡大体と呼び、と表します。

GF(2)上の元｛０，１｝を係数にもつｗ次の既約多項式ｐ（ｘ）を考える。
新しくαという元を考え、ｐ（α）＝０と仮定します。
既約多項式ｐ（ｘ）をうまく選べば、

なる要素はすべて異なり、

を成立させることができる。

これに零元を加えてると、の元の集合となる。

ｐ（α）＝α＾４＋α＋１＝０

この時の要素は以下の１６個の要素よりなる

各要素は多項式に対応し、その係数は4桁の2進数となる。
α＾４＋α＋１＝０なので、α＾４＝-α-１＝α＋１となります。（各係数はGF(2)ですので、１＝－１です。）
この関係をもちいてα^mは３次以下の多項式に変形できます。この多項式の係数が４ビットの２進数に対応します。

指数		α^3	α^2	α^2	α^0	対応する整数値
-∞	０	0	0	0	0	0
０	１	0	0	0	1	1
１	α	0	0	1	0	2
２	α^2	0	1	0	0	4
３	α^3	1	0	0	0	8
４	α^4=1+α	0	0	1	1	3
５	α^5=α(1+α)=α+α^2	0	1	1	0	6
６	α^6=α(α+α^2)=α^2+α^3	1	1	0	0	12
７	α^7=α(α^2+α^3)=α^3+α^4=1+α+α^3	1	0	1	1	11
８	α^8=α(1+α+α^3)=α+α^2+α^4=1+α^2	0	1	0	1	5
９	α^9=α(1+α^2)=α+α^3	1	0	1	0	10
１０	α^10=α(α+α^3)=α^2+α^4=1+α+α^2	0	1	1	1	7
１１	α^11=α(1+α+α^2)=α+α^2+α^3	1	1	1	0	14
１２	α^12=α(α+α^2+α^3)=α^2+α^3+α^4=1+α+α^2+α^3	1	1	1	1	15
１３	α^13=α(1+α+α^2+α^3)=α+α^2+α^3+α^4=1+α^2+α^3	1	1	0	1	13
１４	α^14=α(1+α^2+α^3)=α+α^3+α^4=1+α^3	1	0	0	1	9
１５	α^15=α(1+α^3)=α+α^4=1	0	0	0	1	1

加算は以下のように、各桁ごとにEXORを行います。なぜなら、多項式なので、同じ次数の項のみ加算するのはあたりまえ。

GF(2)で説明したように減算と加算は同じです。

　

乗算は以下のように指数の加算になります。（ここでα^15=1が重要です！）

もう少し複雑な例を示すと、

すなわち、α+α^3（2進数で１０１０）をα^9（指数値で９）に変換し、加算を行い、
結果を逆変換（指数値から2進数）へ変換すると乗算ができます。
この2進数→指数変換TABLEが gflog であり、
指数→2進数変換が gfilog になります。
2進数００００に対応する指数は”-∞”（負の無限大）であり、特別な処理が必要です。

以上　簡単な説明でした。

　

　