はじめに

こんにちは、TechBulkです。 前回は、既約多項式 $h(x)$ で割った余りの世界 $F[X]/h(x)$ が「体」になる、という話をしました。

今回は、この拡大体の構成を「方程式の根（解）を付け足す」という、少し違った（でも本質的には同じ）視点から見ていきます。そして、拡大体の中にある「計算を劇的に簡単にする魔法の構造（巡回群）」について解説します。

1. 複素数とのアナロジー：解がなければ作ればいい

突然ですが、実数 $R$ の世界で方程式 $x^2 + 1 = 0$ を解くことはできますか？ できませんよね。2乗してマイナスになる数は実数には存在しないからです。

そこで数学者たちは、「解がないなら、その解を新しい数として定義してしまおう！」と考えました。これが虚数単位 $i$ です。

• 実数 $R$ に、$x^2+1=0$ の根である $i$ を添加する。
• 新しい世界（複素数体 $C$）では、$a + bi$ という形で数を表す。

実は、符号理論で扱う有限体の拡大も、これと全く同じことをしています。

GF(2) に根を添加する

私たちの基礎となる世界は、0と1だけの $GF(2)$ です。 ここで、前回の成功例である多項式 $\phi(x) = x^3 + x + 1$ を考えます。

実はこの式は、単なる既約多項式ではなく、「原始既約多項式（Primitive Polynomial）」と呼ばれる特別な多項式です。 この方程式の解（根）を $\alpha$ （アルファ）と名付けて、$GF(2)$ に付け足してみましょう。

つまり、$\alpha$ は以下の性質を持つ新しい「数」です。

$$\alpha^3 + \alpha + 1 = 0$$

$GF(2)$ ではマイナスはプラスと同じ（$1 = -1$）なので、移項すると次の重要な等式が得られます。

この等式を使えば、$\alpha^3$ 以上の次数が出てきても、必ず2次以下に書き換えることができます。

2. 拡大体 $GF(2^3)$ の要素を書き出す

$\alpha$ を添加してできる拡大体 $GF(2^3) = GF(8)$ の要素は、$\alpha$ の2次以下の多項式（線形結合）で表されます。 係数は0か1しかないので、組み合わせは $2^3 = 8$ 通りです。

$$S = \{ 0, 1, \alpha, \alpha+1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1 \}$$

これですべての要素が出揃いました。これを「多項式表現」と呼びます。足し算をする時は、この形が便利です（係数同士を $XOR$ すればいいだけなので）。

3. 原始元と巡回群：掛け算を簡単にする仕組み

さて、ここからが今回のハイライトです。 先ほどの「多項式表現」で掛け算を行うのは少し面倒です。毎回 $\alpha^3 = \alpha + 1$ を使って次数を下げる計算が必要だからです。

そこで、$\alpha$ のべき乗（$\alpha^1, \alpha^2, \alpha^3, \dots$）を順に計算して、リスト（表）を作ってみましょう。

べき乗表現	多項式表現への変換	結果
$\alpha^0$	$1$	$1$
$\alpha^1$	$\alpha$	$\alpha$
$\alpha^2$	$\alpha^2$	$\alpha^2$
$\alpha^3$	$\alpha + 1$	$\alpha + 1$
$\alpha^4$	$\alpha(\alpha+1) = \alpha^2 + \alpha$	$\alpha^2 + \alpha$
$\alpha^5$	$\alpha(\alpha^2+\alpha) = \alpha^3 + \alpha^2$	$\alpha^2 + \alpha + 1$
$\alpha^6$	$\alpha(\alpha^2+\alpha+1) = \alpha^3 + \alpha^2 + \alpha$	$\alpha^2 + 1$

次へ行って $\alpha^7$ を計算すると…？

$$\alpha^7 = \alpha(\alpha^2 + 1) = \alpha^3 + \alpha = (\alpha + 1) + \alpha = 1$$

なんと、$1$ （つまり $\alpha^0$）に戻りました！

巡回群（Cyclic Group）

この計算結果からわかる驚くべき事実は以下の2点です。

1. $\alpha^0$ から $\alpha^6$ までの7個の要素は、すべて異なり、$0$ 以外のすべての要素と一致する。
2. $\alpha^7 = 1$ となり、以降はループする（巡回する）。

このように、ある要素（ここでは $\alpha$）のべき乗だけで、その体（$0$を除く）のすべての要素が表現できるとき、その要素 $\alpha$ を「原始元（Primitive Element）」と呼びます。 また、このような構造を「巡回群」と呼びます。

なぜこれが嬉しいのか？

この「べき乗表現」を使うと、掛け算と割り算が圧倒的に簡単になります。 例えば、$\alpha^3 \times \alpha^5$ を計算したいとき、多項式表現だと大変ですが、べき乗表現なら指数法則を使うだけです。

$$\alpha^3 \cdot \alpha^5 = \alpha^{3+5} = \alpha^8$$

$\alpha^7 = 1$ なので、$\alpha^8 = \alpha^7 \cdot \alpha^1 = 1 \cdot \alpha = \alpha$ です。 一瞬で答えが出ました！

対数（log）を使って掛け算を足し算にするのと同じ感覚ですね。この性質は、誤り訂正符号（リード・ソロモン符号など）のエンコード・デコード計算でフル活用されます。

4. まとめ

2回にわたって拡大体の構成を見てきました。

1. 多項式表現: $0$ と $1$ の係数を持つ多項式。加法（足し算）に便利。
2. べき乗表現: 原始元 $\alpha$ の $i$ 乗。乗法（掛け算）に便利。

コンピュータの中で計算する際は、この2つの表現を目的に応じて使い分けることで、複雑な演算を高速に処理しているのです。