情報理論 - ガロア体

概要

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

体

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

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

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

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

ガロア体

体には、要素数が有限のものもあり、これをガロア体(有限体)といい、要素数が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$ は原始多項式であるが、それ以外の全ての原始多項式は奇数個の項を持つ。
  なぜなら、偶数個の項を持つ多項式は、$mod2$ では必ず多項式 $(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{array}{rl}(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{array}$

$\begin{array}{rl}(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{array}$

例.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以上の値の時は、係数に$mod2$を用いて計算する。

• 1次既約多項式

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

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

• 2次既約多項式

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

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

• 3次既約多項式

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

• 4次既約多項式

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

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

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

$\text{上 記 よ り}(a,b,c)=(1,1,1),(1,0,0),(0,0,1)$
したがって、4次既約多項式は、$f(x)=x^4+x^3+x^2+x+1,x^4+x^3+1,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{ℝ}$は、有理数体$\mathbb{\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,{\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+a{x}^2+bx+c(a,b,c\in GF(2))$がGF(2)上で既約であるとは、
$f(0)=c\ne 0$ かつ $f(1)=1+a+b+c\ne 0$であるから、$(a,b,c)=(1,0,1)(0,1,1)$となる場合である。
したがって、GF(2)上の既約多項式は、以下の2つとなる。
$f(x)=x^3+x^2+1,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 \ne 0,\omega \ne 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,{\omega }^3=-\omega -1,{\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,{\omega }^4={\omega }^2+\omega ,{\omega }^5={\omega }^2+\omega +1,{\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,\omega =({\omega }^2+1{)}^{-1}$となり、逆元は$\omega$である。

${\omega }^2+\omega$の逆元
上表から、$(\omega +1)({\omega }^2+\omega )=1,\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,{\omega }^2=({\omega }^2+\omega +1{)}^{-1}$となり、逆元は${\omega }^2$である。

例.4
ωを$x^3+x+1=0$の根とする時、次の値を$a+b\omega +c{\omega }^2(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\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\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$