ガロア体講座

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


Home   ∥ 有元体(ガロア体) | 2元体 | 拡大体 | 応用 | 原始多項式

ガロア体 (Galois field)

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

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

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

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

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

例) 整数を素数5で除算した余りの集合{0,1,2,3,4}

加算のすべての組み合わせを以下に示す。
各行、列に{0,1,2,3,4}の要素がすべて含まれている。

加算

乗算のすべての組み合わせを以下に示す。
零元を除く各行、列に{0,1,2,3,4}の要素がすべて含まれている。

乗算
1

ということで、整数を5で除算した余りの集合{0,1,2,3,4}はガロア体 GF(5) である。
減算では引く数を両辺に足すことにより、加算の表を利用できる。
除算では割る数を両辺に掛けることにより、乗算の表を利用できる。

ページの上部へ

2元体 GF(2)

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

加算

すなわち、加算はXORで、1 + 1 = 0 であるから 1 = -1 となる。

乗算

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

ページの上部へ

拡大体 GF(p

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

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

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

ここで2の要素(元)をもつ体、2のガロア拡大体GF(2)につ いて考える。

まず、GF(2)上の元{0,1}を係数にもつm次の原始多項式p(x)を考える。
新しくαという元を考え、p(α)=0と仮定すると

α0 , α1 , α2 , α3 , ・・・ , αx-2 (ただし x = 2m)

は全て異なる要素となり

αx-1 = 1 (ただし x = 2m)

を成立させることができる。
これに零元を加えると、GF(2)の元のとなる。

GF(2) = {0 , 1 , α , α2 , α3 , ・・・ , αx-2} (ただし x = 2m)

ページの上部へ

の拡大体 GF(2

GF(2)上の4次の原始多項式p(x) = x4 + x + 1 に、
新しくαという元を考え、p(α)=0と仮定すと

p(α) = α4 + α + 1 = 0

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

0 , 1 , α , α2 , α3 , ・・・ , α14

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

指数  多項式 α3 α2 α1 α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) = α+α24 = 1 + α2 0 1 0 1 5
α9 = α(1 + α2) = α + α3 1 0 1 0 10
10 α10 = α(α + α3) = α2 + α4 = 1 + α + α2 0 1 1 1 7
11 α11 = α(1 + α + α2) = α + α2 + α3 1 1 1 0 14
12 α12 = α(α + α2 + α3) = α2 + α3 + α4 = 1 + α + α2 + α3 1 1 1 1 15
13 α13 = α(1 + α + α2 + α3) = α + α2 + α3 + α4 = 1 + α2 + α3 1 1 0 1 13
14 α14 = α(1 + α2 + α3) = α + α3 + α4 = 1 + α3 1 0 0 1 9
15 α15 = α(1 + α3) = α + α4 = 1 0 0 0 1 1

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

α2 + α5 = α2 + (α + α2) = α

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

α2 α5 = α2+5 = α7
α5 α12 = α17 = α15 α2 = α2

複雑になっても

(α + α3)(1 + α + α2 + α3) = α9 α12
= α9+12 = α21 = α6 = α2 + α3

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

ページの上部へ

原始多項式 (primitive polynomial)

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

次数  GF(2)上の原始多項式
 x + 1
 x2 + x + 1
 x3 + x + 1
 x4 + x + 1
 x5 + x2 + 1
 x6 + x + 1
 x7 + x + 1
 x8 + x4 + x3 + x2 + 1
 x9 + x4 + 1
10  x10 + x3 + 1
11  x11 + x2 + 1
12  x12 + x6 + x4 + x + 1
13  x13 + x4 + x3 + x + 1
14  x14 + x10 + x6 + x + 1
15  x15 + x + 1
16  x16 + x12 + x3 + x + 1
17  x17 + x3 + 1
18  x18 + x7 + 1
19  x19 + x5 + x2 + x + 1
20  x20 + x3 + 1
21  x21 + x2 + 1
22  x22 + x + 1
23  x23 + x5 + 1
24  x24 + x7 + x2 + x + 1
25  x25 + x3 + 1
26  x26 + x6 + x2 + x + 1
27  x27 + x5 + x2 + x + 1
28  x28 + x3 + 1
29  x29 + x2 + 1
30  x30 + x23 + x2 + x + 1
31  x31 + x3 + 1
32  x32 + x22 + x2 + x + 1
ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア