Chapter 02
群・環・体 — 「計算できる世界」の分類学
なぜ抽象代数が出てくるのか. 前章で「法\(m\)の世界」を作った。ところがこの先、似たような世界がいくつも出てくる: 多項式の世界、バイトの世界、楕円曲線上の点の世界—— どれも「要素の集合 + 演算」でできていて、似た規則で動いている。
毎回ゼロから性質を調べ直すのは無駄なので、共通の骨組みに名前を付けておく。 それが群・環・体という 3 つの言葉である。
身構える必要はない。要するに次のような分類をしているだけである:
- 群: 演算が 1 つだけあり、引き算（逆向き）ができる
- 環: 足し算と掛け算があるが、割り算はできないかもしれない
- 体: 四則演算が全部できる（0 で割る以外）
ゴールは体である。誤り訂正も暗号も「体の上で計算する」からこそ、 連立方程式が解け、多項式が因数分解でき、逆算ができる。
1. 群 (Group)
定義
集合\(G\)と、その上の 2 項演算\(\ast\)（2 つの要素から 1 つを作る規則）が次の 4 条件を満たすとき、 \((G, \ast)\)を群という。
| # | 名前 | 条件 | 日常語で言うと |
|---|---|---|---|
| 1 | 閉性 | \(a, b \in G \Rightarrow a \ast b \in G\) | 計算しても世界の外に出ない |
| 2 | 結合律 | \((a\ast b)\ast c = a \ast (b \ast c)\) | カッコの付け方を気にしなくてよい |
| 3 | 単位元 | ある\(e\)があって全ての\(a\)で\(a \ast e = e \ast a = a\) | 「何もしない」要素がある |
| 4 | 逆元 | 各\(a\)に対し\(a \ast a^{-1} = e\)なる\(a^{-1}\)がある | 元に戻す操作が必ずある |
さらに\(a \ast b = b \ast a\)（交換律）が成り立つとき可換群（アーベル群）という。
例で確かめる
例 1: 整数と足し算\((\mathbb{Z}, +)\) — 群である。 閉性 ✓（整数どうしの和は整数）、結合律 ✓、単位元は\(0\)、\(a\)の逆元は\(-a\) ✓
例 2: 整数と掛け算\((\mathbb{Z}, \times)\) — 群ではない。 単位元\(1\)はあるが、\(2\)の逆元\(1/2\)が整数でない（条件 4 が破れる）。
例 3: \(\mathbb{Z}_m\)と足し算 — 群である。 単位元\(0\)、\(a\)の逆元は\(m - a\)（\(a + (m-a) = m \equiv 0\)）✓ たとえば法 12 で\(5\)の逆元は\(7\)（\(5+7=12\equiv 0\)）。時計を 5 時間進めてから 7 時間進めると元に戻る。
例 4: \(\mathbb{Z}_m\)の 0 以外と掛け算 — \(m\)が素数のときだけ群になる。 01 章で見たとおり、逆元が存在するのは\(\gcd(a,m)=1\)のとき。 \(m\)が素数ならすべての\(a \in \{1,\dots,m-1\}\)がこれを満たす ✓ \(m\)が合成数だと、\(m\)と共通因数を持つ要素が逆元を持てない ✗
例 4 が本シリーズの分岐点である. 「素数を法にするか、合成数を法にするか」で世界の性質が変わる。 素数なら割り算まで自由にできる豊かな世界（＝体）になり、これが誤り訂正符号の舞台になる。
位数と巡回群
群\(G\)の要素の個数を位数といい\(|G|\)と書く。
要素\(g\)を繰り返し演算して\(g, g^2, g^3, \dots\)と作ったとき、 これで\(G\)の全要素が現れるなら\(g\)を生成元、\(G\)を巡回群という。
例: \((\mathbb{Z}_5^\ast, \times) = \{1,2,3,4\}\)で\(g = 2\)とすると
\(\{2,4,3,1\}\)と全要素が出た。よって\(2\)は生成元で、この群は巡回群 ✓
これが後で効く場面. 「生成元のべき乗で全要素を作れる」という性質は:
- 離散対数問題（17 章）: \(g^x = y\)から\(x\)を求めるのが難しい、という暗号の土台
- LFSR の最長周期（13 章）: 生成元を使うと周期が最大になる
にそのまま使われる。
ラグランジュの定理（後で使う重要事実）
定理: 有限群\(G\)の任意の要素\(a\)について、\(a^{|G|} = e\)（単位元）。
導出のあらまし: \(a\)が生成する部分群\(\langle a \rangle = \{a, a^2, \dots, a^d = e\}\)の位数\(d\)（\(a\)の位数）は、 \(|G|\)を割り切る（部分群の位数は全体の位数を割る = ラグランジュの定理）。 よって\(|G| = dk\)と書けて
これがフェルマーの小定理の正体である. \(G = \mathbb{Z}_p^\ast\)（位数\(p-1\)）に適用すると
$$a^{p-1} \equiv 1 \pmod p$$
が即座に出る。15 章で RSA を作るときの心臓部だが、その本質はこの群論の一般定理であり、 数論の特別な魔法ではない。
2. 環 (Ring)
定義
集合\(R\)に2 つの演算（\(+\) と \(\times\)）があり、次を満たすとき環という:
- \((R, +)\)が可換群（単位元を\(0\)、逆元を\(-a\)と書く）
- \(\times\)が結合律を満たし、単位元\(1\)を持つ
- 分配律: \(a(b+c) = ab + ac\)、\((a+b)c = ac + bc\)
\(ab = ba\)が成り立てば可換環。
要するに「足し算・引き算・掛け算はできるが、割り算は保証されない世界」である。
例
- \(\mathbb{Z}\)（整数全体）: 可換環 ✓（割り算はできない）
- \(\mathbb{Z}_m\)（任意の\(m\)）: 可換環 ✓
- 多項式全体\(\mathbb{Z}[x]\)や\(\mathrm{GF}(2)[x]\): 可換環 ✓（04 章の主役）
- \(n \times n\)行列: 環だが非可換（\(AB \neq BA\)）
零因子 — 環で起きる厄介ごと
\(a \neq 0\)、\(b \neq 0\)なのに\(ab = 0\)となる\(a,b\)を零因子という。
例: \(\mathbb{Z}_{12}\)で\(3 \times 4 = 12 \equiv 0\)。\(3\)も\(4\)も 0 でないのに積が 0。
なぜこれが問題なのか. 普通の数の感覚では「\(ab = 0\)なら\(a=0\)または\(b=0\)」だが、それが崩れる。 すると\(ax = ay \Rightarrow x = y\)という当たり前の式変形が使えなくなる（01 章§2 の割り算の失敗はこれ）。 方程式が解けず、因数分解も一意でなくなる。
零因子が 1 つも無い可換環を整域と呼ぶ。そして「有限の整域は必ず体になる」という定理があり、 これが次節につながる。
3. 体 (Field)
定義
環\(F\)のうち、0 以外のすべての要素が乗法逆元を持つもの（かつ可換）を体という。
言い換えれば「四則演算が完全に自由にできる世界」。 \(+ - \times \div\) が（0 除算を除いて）いつでも実行でき、その結果が必ず世界の中に留まる。
例
| 集合 | 体か | 理由 |
|---|---|---|
| 有理数\(\mathbb{Q}\)、実数\(\mathbb{R}\)、複素数\(\mathbb{C}\) | ✓ | おなじみの体（無限個の要素） |
| 整数\(\mathbb{Z}\) | ✗ | 2 の逆元が無い |
| \(\mathbb{Z}_p\)（\(p\)素数） | ✓ | 有限体。次章の主役 |
| \(\mathbb{Z}_m\)（\(m\)合成数） | ✗ | 零因子があり逆元を持たない要素がある |
定理: \(\mathbb{Z}_m\)が体 \(\iff\) \(m\)が素数
導出:
（\(\Leftarrow\)）\(m = p\)が素数なら、\(1 \le a \le p-1\)のすべてで\(\gcd(a,p) = 1\) （\(p\)の約数は 1 と\(p\)のみで、\(a < p\)だから）。 01 章の定理より逆元が存在 ✓
（\(\Rightarrow\)）\(m\)が合成数なら\(m = ab\)（\(1<a,b<m\)）と書ける。 このとき\(a\)は\(m\)と共通因数\(a\)を持つので\(\gcd(a,m) = a \neq 1\)、よって\(a\)は逆元を持たない ✗ ∎
ここまでで分かったこと. 素数個の要素を持つ世界\(\mathbb{Z}_p\)は、有限なのに四則演算が完全にできる。 これは驚くべきことである。有限個しか数が無いのに、割り算が破綻しない。
この「有限 + 四則演算完備」という性質こそが:
- 誤り訂正で連立方程式を解いて誤り位置を特定できる理由（11 章）
- 暗号で逆算が定義できる理由（16 章）
である。
標数 (characteristic)
体\(F\)で\(\underbrace{1 + 1 + \cdots + 1}_{n\ \text{個}} = 0\)となる最小の正整数\(n\)を標数という （そんな\(n\)が無ければ標数 0）。
- \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\): 標数 0（1 を何回足しても 0 にならない）
- \(\mathbb{Z}_p\): 標数\(p\)
定理: 有限体の標数は必ず素数。
導出: 標数\(n\)が合成数\(n = ab\)（\(1<a,b<n\)）だとする。 体の中で\((\underbrace{1+\cdots+1}_{a})(\underbrace{1+\cdots+1}_{b}) = \underbrace{1+\cdots+1}_{ab} = 0\)。 体には零因子が無い（逆元があるので、\(xy=0\)かつ\(x \neq 0\)なら\(y = x^{-1}xy = 0\)）ので、 どちらかの因子が 0。しかし\(a, b < n\)なので標数の最小性に矛盾 ∎
標数 2 の世界が本シリーズの主戦場である. \(\mathrm{GF}(2) = \{0, 1\}\)は標数 2。ここでは\(1 + 1 = 0\)、つまり 足し算 = XOR になる。 そして\(a + a = 0\)すなわち足し算と引き算が同じという、実装上きわめて便利な性質が生まれる。 CRC も AES も、この性質の上に成り立っている。
4. GF(2) — 最小の体を作ってみる
\(p = 2\)として\(\mathbb{Z}_2 = \{0, 1\}\)を作る。これを\(\mathrm{GF}(2)\)と書く（Galois Field の頭文字）。
加法表（\(\bmod 2\)）:
| \(+\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
乗法表:
| \(\times\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
体の条件を確認する: 0 以外の要素は 1 だけで、\(1 \times 1 = 1\)なので\(1^{-1} = 1\) ✓ 体である。
この 2 つの表の正体. 加法表を見比べてほしい——これはXOR（排他的論理和）そのものである。 乗法表はAND そのもの。
つまり GF(2) の四則演算は、CPU の論理演算 1 命令で実行できる。 ハードウェアで CRC やパリティ計算が高速に動くのは、この一致のおかげである。
さらに標数 2 の性質\(1+1=0\)から、\(a - b = a + b\)（引き算と足し算が同じ）。 符号理論の式で引き算の記号がほとんど出てこないのはこのためである。
5. まとめ — 3 つの言葉の関係
（正確には包含関係ではなく「条件の追加」だが、豊かさの順序はこの通り。）
| 構造 | 演算 | 割り算 | 本シリーズでの例 |
|---|---|---|---|
| 群 | 1 つ | — | 楕円曲線上の点（17 章）、\(\mathbb{Z}_p^\ast\) |
| 環 | 2 つ | ✗ | 多項式\(\mathrm{GF}(2)[x]\)（04 章）、\(\mathbb{Z}_m\) |
| 体 | 2 つ | ✓ | \(\mathrm{GF}(p)\)（03 章）、\(\mathrm{GF}(2^m)\)（05 章） |
この先の道筋:
- 03 章で\(\mathrm{GF}(p)\)を詳しく調べる
- 04 章で「多項式の環」を作る
- 05 章でその環を既約多項式で割って\(\mathrm{GF}(2^m)\)という体を作る （\(\mathbb{Z}\)を素数\(p\)で割って\(\mathbb{Z}_p\)という体を作ったのと、まったく同じ論法）