ガロア体講座

Revised : 2006/07/01
Since : 2006/01/29

ガロア体 (Galois field)

　ガロア体とは整数を素数で除算した余りの集合であり、要素が有限で四則演算が閉じている集合である。

　もう少し詳しく説明すると、集合 F が次の条件 1,2,3 を満たすとき、F は加法・乗法に関して体をなすという。
このとき、有限個の要素からなる体を有限体（finite field）またはガロア体（Galois field）と呼ぶ。
（ガロアは人名。現在の群論・体論・代数論の基礎を築いた数学者。）

1. 集合 F 上に加法・乗法が定義されている。
2. 集合 F に単位元が存在する。（加法の単位元を０、乗法の単位元を１）
3. 集合 F の任意の要素 a に対して、a + b = 0 を満たす加法の逆元:b = -a、
   零元を除いて、a * c = 1 を満たす乗法の逆元:c = a^-1 が存在する。

　どんなガロア体も要素数（濃度）がある素数のべき乗に等しく、かつ、同じ濃度であれば本質的に同じである。
つまり、元（要素）の総数によってガロア体は完全に決定される。
また、集合 F の濃度を ｐ とすれば、濃度 ｐ のガロア体をＧＦ（ｐ）またはF_pと記することとする。
さらに、F_pから零元を除いた集合をF^*_pと記することとする。
a ∈ F^*_pにおいて、aの位数(order)ord(a)とは、a^s = 1となる最小正整数sである。
ord(a) = s　ならば a , a² , ・・・ , a^s はすべて相異なる。

　ガロア体はCRCのようなエラー検出処理、SDRAMや通信で用いられるエラー訂正処理、
AESのような暗号処理などで使われてる数体系である。
　特に、コンピュータの世界では情報を 0 , 1 の二値（ビット）の列にして処理しているため、
通常の数学世界よりGF(2)の方が、ずっと効率良く計算できるのである。

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

加算のすべての組み合わせを以下に示す。
各行、列に｛０，１，２，３，４｝の要素がすべて含まれている。

乗算のすべての組み合わせを以下に示す。
零元を除く各行、列に｛０，１，２，３，４｝の要素がすべて含まれている。

ということで、整数を５で除算した余りの集合｛０，１，２，３，４｝はガロア体 GF(5) である。
減算では引く数を両辺に足すことにより、加算の表を利用できる。
除算では割る数を両辺に掛けることにより、乗算の表を利用できる。

２元体　GF(2)

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

すなわち、加算はXORで、１ ＋ １ ＝ ０ であるから １ ＝ －１ となる。

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

拡大体　GF（ｐ^ｍ）

ある体Ｆがあるとき、体Ｆの元を係数とする代数方程式の解がＦ上に存在するとは限らない。
その「解けない方程式」の解を形式的に用意して、体Ｆに付加することで拡大体を作ることができる。
このような手順で拡大体を作ることを代数拡大（algebraic extension）と呼び、作られた拡大体のことを代数拡大体と呼ぶ。
以下の方法で拡大体を作ることができるが、どの方法も同じことを言っている。

• 体Ｆの範囲では解けない代数方程式 f(x) = 0の解をＦに付加する。
• 体Ｆに対して、条件 f(x) = 0を満たす新しい元ｘを加える。
• 体Ｆ上の多項式Ｆ［ｘ］の変数ｘに対して、条件f(x) = 0を付ける。
• 体Ｆ上の多項式Ｆ［ｘ］を既約多項式f(x) = 0で割ったあまりの集合を作る。
• f(x)を生成元とするイデアルf(x) Ｆ［ｘ］を使って剰余環Ｆ［ｘ］/ｆ（ｘ）Ｆ［ｘ］を作る。

実は、体Ｆの代数拡大体はＦ上の多項式環Ｆ［ｘ］の剰余体になっている。
拡大する多項式の条件は既約であること、すなわち、因数分解できないことである。

多項式の世界で素数に当たるもの (より次数の低い多項式 で割り切れないもの) を既約多項式 (irreducible polynomial) という。
生成多項式が既約でなければ、周期は最大にならない。しかし、既約であっても周期が最大になるとは限らない。
周期が最大になる生成多項式を原始多項式 (primitive polynomial) という。

ここで２^ｍの要素（元）をもつ体、２^ｍのガロア拡大体GF（２^ｍ）につ いて考える。

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

α⁰ , α¹ , α² , α³ , ・・・ , α^x-2 （ただし x = 2^m)

は全て異なる要素となり

α^x-1 = １ （ただし x = 2^m)

を成立させることができる。
これに零元を加えると、GF（２^ｍ）の元のとなる。

GF（２^ｍ） = ｛0 , 1 , α , α² , α³ , ・・・ , α^x-2｝ （ただし x = 2^m)

２^４の拡大体　GF（２^４）

GF(2)上の４次の原始多項式ｐ（ｘ） = ｘ⁴ + ｘ + 1 に、
新しくαという元を考え、ｐ（α）＝０と仮定すと

ｐ（α） = α⁴ + α + 1 = 0

この時の要素は以下の１６個の要素からなる。

0 , 1 , α , α² , α³ , ・・・ , α¹⁴

各要素は多項式に対応し、２元４次元ベクトル：(0,0,0,0)・・・(1,1,1,1)で表せる。
α⁴ + α + 1 = 0 なので、α⁴ = - α - 1 = α + 1 となる。（各係数はGF(2)なので、1 = -1である。）
この関係をもちいてα^mは３次以下の多項式に変形できる。このベクトルが４ビットの２進数に対応する。
また、αは２^４を法とする原始元という。（これはＦ_p（p：素数）の原始根と同様な働きをす る。）

加算は以下のように、各桁ごとにXORを行う。多項式なので、同じ次数の項のみ加算する。

α² + α⁵ = α² + (α + α²) = α

GF(2)と同様に減算と加算は同じでである。
乗算は以下のように指数の加算になる。（ここでα¹⁵ = 1 が重要）

α² α⁵ = α²⁺⁵ = α⁷
α⁵ α¹² = α¹⁷ = α¹⁵ α² = α²

複雑になっても

(α + α³)(1 + α + α² + α³) = α⁹ α¹²
= α⁹⁺¹² = α²¹ = α⁶ = α² + α³

解説すると、α + α³（ベクトル(1,0,1,0) ）をα⁹（指数値９）のように指数に 変換し、指数値の加算を行い、
結果を指数値から多項式へ変換すると乗算ができる。
ベクトル(0,0,0,0)に対応する指数は”-∞”（負の無限大）であり、特別な処理が必要である。

原始多項式 (primitive polynomial)

多項式の世界で素数に当たるもの (より次数の低い多項式 で割り切れないもの) を
既約多項式 (irreducible polynomial) という。
しかし、既約であっても周期が最大になるとは限らない。
周期が最大になる生成多項式を原始多項式 (primitive polynomial) という。