「情報理論 - ガロア体」の版間の差分

📢 Webサイト閉鎖と移転のお知らせ

このWebサイトは2026年9月に閉鎖いたします。

移転先はhttps://mochiu.net/index.php?title=情報理論 - ガロア体です。

新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）

← 古い編集

ビジュアルウィキテキスト

@@ 64行目: / 64行目: @@
 そして、体F上の多項式間の演算は、実数体上の多項式と同様に行う。<br>
 <br>
+==== 原始多項式 ====
+<math>f(x) \in R[X]</math> の全ての係数の最大公約元が単元である時、<math>f(x)</math> は原始多項式(primitive polynomial)という。<br>
+<br>
+例 :<br>
+<math>f(x) = 2x^{3} + 2x^{2} + 2x + 2 \in Z[x]</math> は全ての係数が2で除算できるため原始多項式ではない。<br>
+<math>f(x) = 6x^{2} + 3x + 4 \in Z[x]</math> は原始多項式である。<br>
+<br>
+原始多項式の特徴<br>
+* 全ての最小多項式は既約であるから，原始多項式は既約である。
+* 原始多項式の定数項の係数は、非零でなければならない。<br>そうでないと，多項式xで因数分解できてしまうからである。
+* <math>GF(2)</math> においては、<math>x + 1</math> は原始多項式であるが、それ以外の全ての原始多項式は奇数個の項を持つ。<br>なぜなら、偶数個の項を持つ多項式は、<math>\mod{2}</math> では必ず多項式 <math>(x + 1)</math> で因数分解できてしまうからである。<br>（すなわち、<math>x = 1</math> を根として持つ）
+<br>
 ==== 既約多項式 ====
 体F上の多項式で、それよりも次数の低い体F上多項式に因数分解できない多項式を既約多項式という。<br>
@@ 227行目: / 240行目: @@
 |-
 | style="background-color:#66CCFF;" | <math>\omega</math>
-| 0 || <math>\omega</math> || <math>\omega + 1</math> || <math>\omega</math>
+| 0 || <math>\omega</math> || <math>\omega + 1</math> || 1
 |-
 | style="background-color:#66CCFF;" | <math>\omega + 1</math>
@@ 253行目: / 266行目: @@
 さらに、<math>(x - \omega)(x - \omega^2) = x^2 - x(\omega + \omega^2) + \omega^3 = x^2 + x + 1 = f(x)</math>であるから、原始多項式f(x)はGF(2<sup>2</sup>)で<math>f(x) = (x - \omega)(x - \omega^2)</math>と因数分解される。<br>
 <br>
 ==== GF(2)の3次の拡大体 ====
 GF(2)の2次の拡大体の構成法にならって、GF(2)の3次の拡大体を構成する。<br>
@@ 263行目: / 277行目: @@
 <br>
 GF(2)の3次の拡大体GF(2<sup>3</sup>)を構成するには、まず、GF(2)の3次の既約多項式<math>f(x) = x^3 + x + 1</math>を取り上げる。<br>
+f(x) = 0の根をωとする時、<math>\omega^3 + \omega + 1 = 0</math>となり、したがって、<math>\omega^3 = - \omega - 1 = \omega + 1</math><br>
+また、<math>\omega \ne 0, \quad \omega \ne 1</math>であるから、ωはGF(2)に含まれない。<br>
+<br>
+このωを用いて集合<math>\{ a + b \omega + c \omega^2; a, b, c \in GF(2) \}</math>を作る。<br>
+この集合の要素を全て書くと、<math>\{ 0, 1, \omega, \omega + 1, \omega^2, \omega^2 + 1, \omega^2 + \omega, \omega^2 + \omega + 1 \}</math>となる。<br>
+この8個の要素のどの2つを加算しても、この集合の要素となる。<br>
+ちなみに、3次の既約多項式<math>f(x) = x^3 + x + 1</math> を用いる場合、<math>\omega^3 + \omega + 1 = 0, \quad \omega^3 = - \omega - 1, \quad \omega^3 = \omega + 1</math>となる。<br>
+<br>
+すなわち、この集合の和は閉じている。差においても閉じていることは明らかである。<br>
+<br>
+下表に、この集合(GF(2)の3次の拡大体GF(2<sup>3</sup>))の積の演算を示す。<br>
+<center>
+{| class="wikitable" | style="text-align: center; background-color:#fefefe;"
+|-
+! style="background-color:#66CCFF;" | 積
+! style="background-color:#66CCFF;" | 1
+! style="background-color:#66CCFF;" | <math>\omega</math>
+! style="background-color:#66CCFF;" | <math>\omega + 1</math>
+! style="background-color:#66CCFF;" | <math>\omega^2</math>
+! style="background-color:#66CCFF;" | <math>\omega^2 + 1</math>
+! style="background-color:#66CCFF;" | <math>\omega^2 + \omega</math>
+! style="background-color:#66CCFF;" | <math>\omega^2 + \omega + 1</math>
+|-
+| style="background-color:#66CCFF;" | 1
+| 1 || <math>\omega</math> || <math>\omega + 1</math> || <math>\omega^2</math> || <math>\omega^2 + 1</math> || <math>\omega^2 + \omega</math> || <math>\omega^2 + \omega + 1</math>
+|-
+| style="background-color:#66CCFF;" | <math>\omega</math>
+| <math>\omega</math> || <math>\omega^2</math> || <math>\omega^2 + \omega</math> || <math>\omega + 1</math> || 1 || <math>\omega^2 + \omega + 1</math> || <math>\omega^2 + 1</math>
+|-
+| style="background-color:#66CCFF;" | <math>\omega + 1</math>
+| <math>\omega + 1</math> || <math>\omega^2 + \omega</math> || <math>\omega^2 + 1</math> || <math>\omega^2 + \omega + 1</math> || <math>\omega^2</math> || 1 || <math>\omega</math>
+|-
+| style="background-color:#66CCFF;" | <math>\omega^2</math>
+| <math>\omega^2</math> || <math>\omega + 1</math> || <math>\omega^2 + \omega + 1</math> || <math>\omega^2 + \omega</math> || <math>\omega</math> || <math>\omega^2 + 1</math> || 1
+|-
+| style="background-color:#66CCFF;" | <math>\omega^2 + 1</math>
+| <math>\omega^2 + 1</math> || 1 || <math>\omega^2</math> || <math>\omega</math> || <math>\omega^2 + \omega + 1</math> || <math>\omega + 1</math> || <math>\omega^2 + \omega</math>
+|-
+| style="background-color:#66CCFF;" | <math>\omega^2 + \omega</math>
+| <math>\omega^2 + \omega</math> || <math>\omega^2 + \omega + 1</math> || 1 || <math>\omega^2 + 1</math> || <math>\omega + 1</math> || <math>\omega</math> || <math>\omega^2</math>
+|-
+| style="background-color:#66CCFF;" | <math>\omega^2 + \omega + 1</math>
+| <math>\omega^2 + \omega + 1</math> || <math>\omega^2 + 1</math> || <math>\omega</math> || 1 || <math>\omega^2 + \omega</math> || <math>\omega^2</math> || <math>\omega + 1</math>
+|}
+</center>
+<br>
+ 例.1<br>
+ <math>\omega^2 (1 + \omega + \omega^2) = \omega^2 + \omega^3 + \omega^4 = \omega^2 + \omega + 1 + \omega (\omega + 1) = 1</math>
+<br>
+ 例.2<br>
+ <math>\omega^2 + \omega + 1</math>の逆元は、積が1となる元<math>\omega^2</math>である。
+ <math>\omega^2 (\omega^2 + \omega + 1) = 1</math>より、<math>\omega^2 = \frac{1}{\omega^2 + \omega + 1}</math>である。
+ 例えば、<math>\frac{\omega}{\omega^2 + \omega + 1} = \omega \times \omega^2 = \omega^3 = \omega + 1</math>となる。
+<br>
+上式のように、ωを<math>\omega^2 + \omega + 1</math>で割った結果もこの集合の要素となる。<br>
+同様に、商に関しても閉じていることが分かる。<br>
+<br>
+以上のように、集合<math>\{ 0, 1, \omega, \omega + 1, \omega^2, \omega^2 + 1, \omega^2 + \omega, \omega^2 + \omega + 1 \}</math>は、四則に関して閉じているため、体である。<br>
+<u>この体をGF(2<sup>3</sup>)と表し、GF(2)の3次拡大体という。</u><br>
+<br>
+GF(2<sup>3</sup>)の累乗表示において、<math>\omega^3 = \omega + 1, \quad \omega^4 = \omega^2 + \omega, \quad \omega^5 = \omega^2 + \omega + 1, \quad \omega^6 = \omega^2 + 1</math>となる。<br>
+このように、GF(2<sup>3</sup>)の要素は、ωの累乗で表されることがわかる。<br>
+したがって、GF(2<sup>3</sup>)は、以下の2つの表示をすることができる。<br>
+* <math>GF(2^3) = \{ 0, 1, \omega, \omega + 1, \omega^2, \omega^2 + 1, \omega^2 + \omega, \omega^2 + \omega + 1 \}</math><br><math>\Rightarrow \{ a + b \omega + c \omega^2; a, b, c \in GF(2) \}</math>
+* <math>GF(2^3) = \{ 0, 1, \omega, \omega^2, \omega^3, \omega^4, \omega^5, \omega^6 \}</math><br><math>\Rightarrow \{ 0, \omega^{i}; 0, 1, 2, \cdots, 6 \}</math>
+<br>
+ωはGF(2<sup>3</sup>)の原始根、<math>f(x) = x^3 + x + 1</math>はGF(2<sup>3</sup>)の原始多項式である。<br>
+<br>
+GF(2<sup>3</sup>)の原始多項式<math>f(x) = x^3 + x + 1</math>の因数分解は、<math>f(x) = (x - \omega)(x - \omega^2)(x - \omega^4)</math>となる。<br>
+また、GF(2)上のもう1つの3次の既約多項式<math>g(x) = x^3 + x^2 + 1</math>は、<math>g(x) = (x - \omega^3)(x - \omega^5)(x - \omega^7)</math>と因数分解される。<br>
+したがって、GF(2)では3次の既約多項式として、<math>f(x) = x^3 + x + 1</math>の代わりに<math>g(x) = x^3 + x^2 + 1</math>を用いても、同じ3次の拡大体GF(2<sup>3</sup>)が得られる。<br>
+<br>
+ 例.3
+ 上表(GF(2)の3次の拡大体GF(2<sup>3</sup>)の積の演算表)を用いて、GF(2<sup>3</sup>)内の次の要素の逆元を求める。
+ <math>\omega^2 + 1</math>の逆元
+ 上表から、<math>\omega (\omega^2 + 1) = 1, \quad \omega = (\omega^2 + 1)^{-1}</math>となり、逆元は<math>\omega</math>である。
+ <math>\omega^2 + \omega</math>の逆元
+ 上表から、<math>(\omega + 1)(\omega^2 + \omega) = 1, \quad \omega + 1 = (\omega^2 + \omega)^{-1}</math>となり、逆元は<math>\omega + 1</math>である。
+ <math>\omega^5</math>の逆元
+ <math>\omega^5 = \omega^2(\omega + 1) = \omega^3 + \omega^2 = \omega^2 + \omega + 1</math>である。
+ 上表から、<math>\omega^2 (\omega^2 + \omega + 1) = 1, \quad \omega^2 = (\omega^2 + \omega + 1)^{-1}</math>となり、逆元は<math>\omega^2</math>である。
+<br>
+ 例.4
+ ωを<math>x^3 + x + 1 = 0</math>の根とする時、次の値を<math>a + b \omega + c \omega^2 \quad (a, b, c \in GF(2))</math>の形で表す。
+. <math>\frac{\omega^2}{\omega^2 + \omega}</math>
+ <math>\frac{1}{\omega^2 + \omega}</math>は、<math>(\omega + 1)(\omega^2 + \omega) = 1</math>より、<math>\frac{1}{\omega^2 + \omega} = \omega + 1 \quad \cdots (1)</math>
+ (1)式より、<math>\frac{\omega^2}{\omega^2 + \omega} = \omega^2 (\omega + 1) = \omega^3 + \omega^2 = \omega^2 + \omega + 1</math>となる。
+. <math>\frac{\omega^2 + \omega + 1}{\omega^4}</math>
+ <math>\frac{1}{\omega^4} = \frac{1}{\omega^2 + \omega}</math>は、<math>(\omega + 1)(\omega^2 + \omega) = 1</math>より、<math>\frac{1}{\omega^2 + \omega} = \omega + 1 \quad \cdots (2)</math>
+ (2)式より、<math>\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</math>
 <br><br>
 __FORCETOC__
 [[カテゴリ:情報理論]]