情報理論 - ガロア体

概要

誤り検出能力や誤り訂正能力を高めるための基礎的な理論には、体と拡大体の考え方が用いられる。
ここでは、体と拡大体の基本的な考え方を記載する。

体

有理数の全体を$\mathbb {Q}$とする時、$\mathbb {Q}$は四則で閉じている。
すなわち、$a,b\in \mathbb {Q}$ とすると、以下が成り立つ。
$a+b,\quad a-b,\quad ab,\quad b\neq 0{\mbox{ の と き }}{\frac {a}{b}}$

同様に、実数の全体を$\mathbb {R}$とする時、$\mathbb {R}$も四則で閉じている。

集合$\mathbb {Q} ,\mathbb {R}$に限らず、四則で閉じている集合を体という。
特に、集合$\mathbb {Q}$を有理数体、集合$\mathbb {R}$を実数体という。

下図に、群環体の定義を示す。

ガロア体

体には、要素数が有限のものもあり、これをガロア体(有限体)といい、要素数がq個であるガロア体をGF(q)で表す。
特に、GF(2)は0と1の要素から成り、加法と乗法の演算は下表のようになる。
GF(2)のことを、Z/2Zで表すこともある。

GF(2)の加法演算では、1 + 1 = 0となることに注意すること。

また、加法についての単位元は0、乗法についての単位元は1である。

GF(2)の加法演算

+	0	1
0	0	1
1	1	0

GF(2)の乗法演算

×	0	1
0	0	0
1	0	1

多項式

体F上の多項式

体Fの要素を係数とする多項式を、体F上の多項式と呼ぶ。
そして、体F上の多項式間の演算は、実数体上の多項式と同様に行う。

原始多項式

$f(x)\in R[X]$ の全ての係数の最大公約元が単元である時、$f(x)$ は原始多項式(primitive polynomial)という。

例 :
$f(x)=2x^{3}+2x^{2}+2x+2\in Z[x]$ は全ての係数が2で除算できるため原始多項式ではない。
$f(x)=6x^{2}+3x+4\in Z[x]$ は原始多項式である。

原始多項式の特徴

• 全ての最小多項式は既約であるから，原始多項式は既約である。
• 原始多項式の定数項の係数は、非零でなければならない。
  そうでないと，多項式xで因数分解できてしまうからである。
• $GF(2)$ においては、$x+1$ は原始多項式であるが、それ以外の全ての原始多項式は奇数個の項を持つ。
  なぜなら、偶数個の項を持つ多項式は、$\mod {2}$ では必ず多項式 $(x+1)$ で因数分解できてしまうからである。
  （すなわち、$x=1$ を根として持つ）

既約多項式

体F上の多項式で、それよりも次数の低い体F上多項式に因数分解できない多項式を既約多項式という。
特に、次数がmである時、m次既約多項式という。

例.1
多項式$1+x^{2},1+x+x^{2},1+x+x^{3}$は、全ての係数がGF(2)の要素0、1であるから、GF(2)上の多項式である。
${\begin{aligned}(1+x+x^{2})+(1+x+x^{3})&=(1+1)+(x+x)+x^{2}+x^{3}\\&=(1+1)+x(1+1)+x^{2}+x^{3}\\&=0+x\times 0+x^{2}+x^{3}\\&=x^{2}+x^{3}\end{aligned}}$

${\begin{aligned}(1+x^{2})(1+x+x^{3})&=1+x+x^{3}+x^{2}+x^{3}+x^{5}\\&=1+x+x^{2}+(x^{3}+x^{3})+x^{5}\\&=1+x+x^{2}+x^{5}\end{aligned}}$

例.2
多項式$1+x+x^{3}$ と $1+x^{2}+x^{3}$ は、GF(2)上の3次の既約多項式である。

例.3
5次多項式$1+x+x^{2}+x^{5}$ は、$(1+x^{2})(1+x+x^{3})$と因数分解できるため、既約多項式ではない。

GF(2)の既約多項式の求め方

m次の既約多項式を求めるには、まず、m次の次数が存在する必要がある。(例. 3次既約多項式ではx³、5次既約多項式ではx⁵等)

$GF(2)=\{0,1\}$ のため、係数は0、 1のいずれかである。
もし、係数が2以上の値の時は、係数に${\bmod {2}}$を用いて計算する。

• 1次既約多項式

GF(2)上の1次既約多項式を求めるには、$f(x)=ax+b$において、因数分解できないため、1次既約多項式は、$x,\quad x+1$の2つである。

2次以降の既約多項式では、必ず定数項を含むことに注意する。
なぜなら、定数項が存在しない場合、$f(0)=0$となり、また、f(x)は1次既約多項式xで可約だから(因数分解できるから)である。

• 2次既約多項式

2次既約多項式を求めるには、$f(x)=x^{2}+ax+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =1$ (床関数)だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
(床関数とは、$n\leq x<n+1$を満たす整数nのことを$\lfloor x\rfloor$と記述する。$\lfloor x\rfloor$は、xを超えない最大の整数とも言える。)

$f(0)=1\neq 0$
$f(1)=1+a+1=a\neq 0\quad {\mbox{す な わ ち}}\quad a=1$
したがって、2次既約多項式は、$f(x)=x^{2}+x+1$となる。

• 3次既約多項式

3次既約多項式を求めるには、$f(x)=x^{3}+ax^{2}+bx+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =1$だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
$f(0)=1\neq 0$
$f(1)=1+a+b+1=a+b\neq 0\quad {\mbox{す な わ ち}}\quad (a,b)=(1,0)\quad {\mbox{ま た は}}\quad (0,1)$
したがって、3次既約多項式は、$f(x)=x^{3}+x^{2}+1,\quad f(x)=x^{3}+x+1$ の2つとなる。

• 4次既約多項式

4次既約多項式を求めるには、$f(x)=x^{4}+ax^{3}+bx^{2}+cx+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =2$だから、
f(x)が2次以下の既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
$f(0)=1\neq 0$
$f(1)=1+a+b+c+1=a+b+c\neq 0\quad {\mbox{し た が っ て}}\quad a+b+c=1$

f(x)を2次の既約多項式$x^{2}+x+1$で割った剰余は、$x(b+c+1)+(a+b+1)$

$b+c+1,\quad a+b+1$が同時に0になってはならないため、$b+c=0\quad {\mbox{ま た は}}\quad a+b=0$
$a+b=0\quad {\mbox{の 時 、}}\quad a+b+c=c=1\quad {\mbox{し た が っ て}}\quad (a,b)=(0,0),(1,1)\quad {\mbox{よ り}}\quad (a,b,c)=(0,0,1),(1,1,1)$
$b+c=0\quad {\mbox{の 時 、}}\quad a+b+c=a=1\quad {\mbox{し た が っ て}}\quad (b,c)=(0,0),(1,1)\quad {\mbox{よ り}}\quad (a,b,c)=(1,0,0),(1,1,1)$

${\mbox{上 記 よ り}}\quad (a,b,c)=(1,1,1),(1,0,0),(0,0,1)$
したがって、4次既約多項式は、$f(x)=x^{4}+x^{3}+x^{2}+x+1,\quad x^{4}+x^{3}+1,\quad x^{4}+x+1$ の3つとなる。

5次既約多項式を、以下に示す。

• x
• 1 + x

  
  

• 1 + x + x²

  
  

• 1 + x + x³
• 1 + x + x³

  
  

• 1 + x³ + x⁴
• 1 + x + x² + x³ + x⁴
• 1 + x + x⁴

  
  

• 1 + x³ + x⁵
• 1 + x² + x⁵
• 1 + x + x² + x³ + x⁵
• 1 + x + x³ + x⁴ + x⁵
• 1 + x² + x³ + x⁴ + x⁵
• 1 + x + x² + x⁴ + x⁵

拡大体

体Kが体F上を含む時、体Kを体Fの拡大体という。
実数体$\mathbb {R}$は、有理数体$\mathbb {Q}$の拡大体である。
体F上の既約多項式f(x)がある時、方程式f(x) = 0の根ωを用いて、体Fの拡大体Kを作ることができる。

GF(2)の2次の拡大体

GF(2)上の2次の既約多項式は、$f(x)=x^{2}+x+1$だけである。

f(x) = 0の根をωとすると、$\omega ^{2}+\omega +1=0$が成り立つ。
このωを用いて、集合$\{a+b\omega ;a,b\in GF(2)\}$を作ると、この集合は体となる。

a、bは0か1であるから、この集合の要素は$\{0,1,\omega ,\omega +1\}$となる。
この集合の任意の2要素の和もこの集合に属する。
また、この集合の任意の2要素の積もこの集合に属する。

例.1
$\omega +\omega =\omega (1+1)=\omega \times 0=0$より、$\omega =-\omega$である。
これは、GF(2)では、加えることと減ずることは同じことを意味する。

例.2
$\omega +(1+\omega )=1+(\omega +\omega )=1+0=1$

例.3
2次の既約多項式$f(x)=x^{2}+x+1$において、f(x) = 0の根をωとすると、$\omega ^{2}+\omega +1=0$より、$\omega ^{2}=-\omega -1$
また、$(\omega +1)+(\omega +1)=0$より、$\omega +1=-\omega -1$
したがって、 $\omega ^{2}=-\omega -1=\omega +1$

例.4
$\omega (1+\omega )=\omega +\omega ^{2}=\omega +\omega +1=0+1=1$

下表に、GF(2)の2次の拡大体の演算を示す。

和	0	1	$\omega$	$\omega +1$
0	0	1	$\omega$	$\omega +1$
1	1	0	$\omega +1$	$\omega$
$\omega$	$\omega$	$\omega +1$	0	1
$\omega +1$	$\omega +1$	$\omega$	1	0

積	0	1	$\omega$	$\omega +1$
0	0	0	0	0
1	0	1	$\omega$	$\omega +1$
$\omega$	0	$\omega$	$\omega +1$	1
$\omega +1$	0	$\omega +1$	1	$\omega$

また、これらは商に関しても閉じている。
上表より、$\omega (1+\omega )=1$であるから、$\omega =(\omega +1)^{-1}$である。
これは、$1+\omega$の逆元$(1+\omega )^{-1}$は、$1+\omega$との積が1となる元であることを意味する。
${\frac {\omega }{1+\omega }}=\omega (1+\omega )^{-1}=\omega \times \omega =\omega ^{2}=\omega +1$

以上のように、集合$\{0,1,\omega ,\omega +1\}$は、四則において閉じており、体である。
この体のことをGF(2²)と表し、GF(2)の2次の拡大体という。

GF(2²)の要素の累乗表示において、$\omega ^{2}=\omega +1,\quad \omega ^{3}=\omega \times \omega ^{2}=\omega (\omega +1)=1$より、
$GF(2^{2})=\{0,1,\omega ,\omega ^{2}\}$となる。
すなわち、集合GF(2²)は、以下の2つの表示をすることができる。

• 線形表示

  $GF(2^{2})=\{0,1,\omega ,\omega +1\}$ まとめて $\{a+b\omega ;a,b\in GF(2)\}$

• 累乗表示

  $GF(2^{2})=\{0,1,\omega ,\omega ^{2}\}$ まとめて $\{0,\omega ^{i};i=0,1,2\}$

累乗表示の性質から、ωをGF(2²)の原始根といい、ωを根にもつ$f(x)=x^{2}+x+1$をGF(2²)の原始多項式という。
さらに、$(x-\omega )(x-\omega ^{2})=x^{2}-x(\omega +\omega ^{2})+\omega ^{3}=x^{2}+x+1=f(x)$であるから、原始多項式f(x)はGF(2²)で$f(x)=(x-\omega )(x-\omega ^{2})$と因数分解される。

GF(2)の3次の拡大体

GF(2)の2次の拡大体の構成法にならって、GF(2)の3次の拡大体を構成する。

まず、GF(2)上の3次の既約多項式を求める。
GF(2)上の3次の多項式$f(x)=x^{3}+ax^{2}+bx+c\quad (a,b,c\in GF(2))$がGF(2)上で既約であるとは、
$f(0)=c\neq 0$ かつ $f(1)=1+a+b+c\neq 0$であるから、$(a,b,c)=(1,0,1)\quad (0,1,1)$となる場合である。
したがって、GF(2)上の既約多項式は、以下の2つとなる。
$f(x)=x^{3}+x^{2}+1,\quad f(x)=x^{3}+x+1$

GF(2)の3次の拡大体GF(2³)を構成するには、まず、GF(2)の3次の既約多項式$f(x)=x^{3}+x+1$を取り上げる。
f(x) = 0の根をωとする時、$\omega ^{3}+\omega +1=0$となり、したがって、$\omega ^{3}=-\omega -1=\omega +1$
また、$\omega \neq 0,\quad \omega \neq 1$であるから、ωはGF(2)に含まれない。

このωを用いて集合$\{a+b\omega +c\omega ^{2};a,b,c\in GF(2)\}$を作る。
この集合の要素を全て書くと、$\{0,1,\omega ,\omega +1,\omega ^{2},\omega ^{2}+1,\omega ^{2}+\omega ,\omega ^{2}+\omega +1\}$となる。
この8個の要素のどの2つを加算しても、この集合の要素となる。
ちなみに、3次の既約多項式$f(x)=x^{3}+x+1$ を用いる場合、$\omega ^{3}+\omega +1=0,\quad \omega ^{3}=-\omega -1,\quad \omega ^{3}=\omega +1$となる。

すなわち、この集合の和は閉じている。差においても閉じていることは明らかである。

下表に、この集合(GF(2)の3次の拡大体GF(2³))の積の演算を示す。

積	1	$\omega$	$\omega +1$	$\omega ^{2}$	$\omega ^{2}+1$	$\omega ^{2}+\omega$	$\omega ^{2}+\omega +1$
1	1	$\omega$	$\omega +1$	$\omega ^{2}$	$\omega ^{2}+1$	$\omega ^{2}+\omega$	$\omega ^{2}+\omega +1$
$\omega$	$\omega$	$\omega ^{2}$	$\omega ^{2}+\omega$	$\omega +1$	1	$\omega ^{2}+\omega +1$	$\omega ^{2}+1$
$\omega +1$	$\omega +1$	$\omega ^{2}+\omega$	$\omega ^{2}+1$	$\omega ^{2}+\omega +1$	$\omega ^{2}$	1	$\omega$
$\omega ^{2}$	$\omega ^{2}$	$\omega +1$	$\omega ^{2}+\omega +1$	$\omega ^{2}+\omega$	$\omega$	$\omega ^{2}+1$	1
$\omega ^{2}+1$	$\omega ^{2}+1$	1	$\omega ^{2}$	$\omega$	$\omega ^{2}+\omega +1$	$\omega +1$	$\omega ^{2}+\omega$
$\omega ^{2}+\omega$	$\omega ^{2}+\omega$	$\omega ^{2}+\omega +1$	1	$\omega ^{2}+1$	$\omega +1$	$\omega$	$\omega ^{2}$
$\omega ^{2}+\omega +1$	$\omega ^{2}+\omega +1$	$\omega ^{2}+1$	$\omega$	1	$\omega ^{2}+\omega$	$\omega ^{2}$	$\omega +1$

例.1

$\omega ^{2}(1+\omega +\omega ^{2})=\omega ^{2}+\omega ^{3}+\omega ^{4}=\omega ^{2}+\omega +1+\omega (\omega +1)=1$

例.2

$\omega ^{2}+\omega +1$の逆元は、積が1となる元$\omega ^{2}$である。
$\omega ^{2}(\omega ^{2}+\omega +1)=1$より、$\omega ^{2}={\frac {1}{\omega ^{2}+\omega +1}}$である。
例えば、${\frac {\omega }{\omega ^{2}+\omega +1}}=\omega \times \omega ^{2}=\omega ^{3}=\omega +1$となる。

上式のように、ωを$\omega ^{2}+\omega +1$で割った結果もこの集合の要素となる。
同様に、商に関しても閉じていることが分かる。

以上のように、集合$\{0,1,\omega ,\omega +1,\omega ^{2},\omega ^{2}+1,\omega ^{2}+\omega ,\omega ^{2}+\omega +1\}$は、四則に関して閉じているため、体である。
この体をGF(2³)と表し、GF(2)の3次拡大体という。

GF(2³)の累乗表示において、$\omega ^{3}=\omega +1,\quad \omega ^{4}=\omega ^{2}+\omega ,\quad \omega ^{5}=\omega ^{2}+\omega +1,\quad \omega ^{6}=\omega ^{2}+1$となる。
このように、GF(2³)の要素は、ωの累乗で表されることがわかる。
したがって、GF(2³)は、以下の2つの表示をすることができる。

• $GF(2^{3})=\{0,1,\omega ,\omega +1,\omega ^{2},\omega ^{2}+1,\omega ^{2}+\omega ,\omega ^{2}+\omega +1\}$
  $\Rightarrow \{a+b\omega +c\omega ^{2};a,b,c\in GF(2)\}$
• $GF(2^{3})=\{0,1,\omega ,\omega ^{2},\omega ^{3},\omega ^{4},\omega ^{5},\omega ^{6}\}$
  $\Rightarrow \{0,\omega ^{i};0,1,2,\cdots ,6\}$

ωはGF(2³)の原始根、$f(x)=x^{3}+x+1$はGF(2³)の原始多項式である。

GF(2³)の原始多項式$f(x)=x^{3}+x+1$の因数分解は、$f(x)=(x-\omega )(x-\omega ^{2})(x-\omega ^{4})$となる。
また、GF(2)上のもう1つの3次の既約多項式$g(x)=x^{3}+x^{2}+1$は、$g(x)=(x-\omega ^{3})(x-\omega ^{5})(x-\omega ^{7})$と因数分解される。
したがって、GF(2)では3次の既約多項式として、$f(x)=x^{3}+x+1$の代わりに$g(x)=x^{3}+x^{2}+1$を用いても、同じ3次の拡大体GF(2³)が得られる。

例.3
上表(GF(2)の3次の拡大体GF(23)の積の演算表)を用いて、GF(23)内の次の要素の逆元を求める。

$\omega ^{2}+1$の逆元
上表から、$\omega (\omega ^{2}+1)=1,\quad \omega =(\omega ^{2}+1)^{-1}$となり、逆元は$\omega$である。

$\omega ^{2}+\omega$の逆元
上表から、$(\omega +1)(\omega ^{2}+\omega )=1,\quad \omega +1=(\omega ^{2}+\omega )^{-1}$となり、逆元は$\omega +1$である。

$\omega ^{5}$の逆元
$\omega ^{5}=\omega ^{2}(\omega +1)=\omega ^{3}+\omega ^{2}=\omega ^{2}+\omega +1$である。
上表から、$\omega ^{2}(\omega ^{2}+\omega +1)=1,\quad \omega ^{2}=(\omega ^{2}+\omega +1)^{-1}$となり、逆元は$\omega ^{2}$である。

例.4
ωを$x^{3}+x+1=0$の根とする時、次の値を$a+b\omega +c\omega ^{2}\quad (a,b,c\in GF(2))$の形で表す。

1. ${\frac {\omega ^{2}}{\omega ^{2}+\omega }}$
${\frac {1}{\omega ^{2}+\omega }}$は、$(\omega +1)(\omega ^{2}+\omega )=1$より、${\frac {1}{\omega ^{2}+\omega }}=\omega +1\quad \cdots (1)$
(1)式より、${\frac {\omega ^{2}}{\omega ^{2}+\omega }}=\omega ^{2}(\omega +1)=\omega ^{3}+\omega ^{2}=\omega ^{2}+\omega +1$となる。


2. ${\frac {\omega ^{2}+\omega +1}{\omega ^{4}}}$
${\frac {1}{\omega ^{4}}}={\frac {1}{\omega ^{2}+\omega }}$は、$(\omega +1)(\omega ^{2}+\omega )=1$より、${\frac {1}{\omega ^{2}+\omega }}=\omega +1\quad \cdots (2)$
(2)式より、${\frac {\omega ^{2}+\omega +1}{\omega ^{4}}}=(\omega ^{2}+\omega +1)(\omega +1)=\omega ^{3}+\omega ^{2}+\omega +\omega ^{2}+\omega +1=\omega ^{3}+1=\omega$