Chapter 02
群・環・体 — 「計算できる世界」の分類学
なぜ抽象代数が出てくるのか. 01 章で、\(m\)で割った余りだけを考える世界\(\mathbb{Z}_m\)を作った。この先には似た世界がいくつも出てくる。 多項式の世界、8 ビットのまとまりであるバイトの世界、楕円曲線上の点の世界。 どれも「要素の集合と、その上の演算」でできていて、同じ規則で動いている。
毎回ゼロから性質を調べ直すのは無駄なので、共通の骨組みに名前を付けておく。 それが群・環・体という 3 つの言葉である。 分類の基準は「演算がいくつあるか」と「それぞれの演算を打ち消せるか」の 2 つだけである。
- 群: 演算が 1 つ。その演算は必ず打ち消せる
- 環: 演算が 2 つ。足し算は必ず打ち消せるが、掛け算は打ち消せる保証がない
- 体: 演算が 2 つ。0 で割る場合を除き、どちらも必ず打ち消せる
「打ち消せる」の正確な意味は 1 節の定義で与える。 ゴールは体である。誤り訂正も暗号も体の上で計算するからこそ、連立方程式が解け、多項式が因数分解でき、逆算ができる。
1. 群 (Group)
定義
集合\(G\)と、その上の 2 項演算\(\ast\)が次の 4 条件を満たすとき、\((G, \ast)\)を群という。 2 項演算とは、2 つの要素から 1 つの要素を作る規則のことである。
| # | 名前 | 条件 | 意味 |
|---|---|---|---|
| 1 | 閉性 | \(a, b \in G \Rightarrow a \ast b \in G\) | 演算の結果が\(G\)の外に出ない |
| 2 | 結合律 | \((a\ast b)\ast c = a \ast (b \ast c)\) | 3 つ以上を演算するとき、どこから計算しても同じ |
| 3 | 単位元 | ある\(e\)があって全ての\(a\)で\(a \ast e = e \ast a = a\) | 演算しても相手を変えない要素がある |
| 4 | 逆元 | 各\(a\)に対し\(a \ast a^{-1} = a^{-1} \ast a = e\)なる\(a^{-1}\)がある | どの要素も打ち消せる |
さらに\(a \ast b = b \ast a\)（交換律）が成り立つとき可換群という。アーベル群は同じものの別名である。
単位元と逆元は演算ごとに決まる。足し算なら単位元は\(0\)、\(a\)の逆元は\(-a\)である。 掛け算なら単位元は\(1\)、\(a\)の逆元は\(1/a\)である。 引き算と割り算は独立した演算ではなく、逆元との演算の略記として扱う。 \(a - b\)は\(a + (-b)\)、\(a \div b\)は\(a \times b^{-1}\)の意味である。 冒頭で「打ち消せる」と呼んだのは、この逆元が必ず存在することを指す。
例で確かめる
例 1: 整数と足し算\((\mathbb{Z}, +)\) — 群である。 整数どうしの和は整数なので閉性を満たし、結合律も成り立つ。単位元は\(0\)、\(a\)の逆元は\(-a\)である。 引き算\(5 - 3\)は\(5 + (-3)\)の略記であり、逆元があるから引ける。
例 2: 整数と掛け算\((\mathbb{Z}, \times)\) — 群ではない。 単位元\(1\)はあるが、\(2\)の逆元\(1/2\)が整数でないので条件 4 が破れる。 掛け算を打ち消す割り算が、整数の中ではできない。
例 3: \(\mathbb{Z}_m\)と足し算 — 群である。 \(\mathbb{Z}_m\)は01 章で定義した法\(m\)の世界\(\{0, 1, \dots, m-1\}\)で、\(m\)以上の数は\(m\)で割った余りに置き換える。 たとえば\(m = 5\)なら\(\mathbb{Z}_5 = \{0,1,2,3,4\}\)であり、\(5\)は\(0\)と同じものとして扱う。 単位元は\(0\)、\(a\)の逆元は\(m - a\)である。\(a + (m-a) = m \equiv 0\)だからである。 法 12 で\(5\)の逆元は\(7\)であり、時計を 5 時間進めてから 7 時間進めると元に戻る。
例 4: \(\mathbb{Z}_m\)の 0 以外と掛け算 — \(m\)が素数のときだけ群になる。 \(0\)を除くのは、\(0 \times x = 1\)となる\(x\)が存在しないからである。 01 章で見たとおり、\(a\)が掛け算の逆元を持つのは\(\gcd(a,m)=1\)のときである。 \(m\)が素数ならすべての\(a \in \{1,\dots,m-1\}\)がこれを満たす。 \(m\)が合成数だと、\(m\)と共通因数を持つ要素が逆元を持てない。
記法: \(\mathbb{Z}_m\)のうち掛け算の逆元を持つ要素、すなわち\(m\)と互いに素な要素だけを集めた集合を\(\mathbb{Z}_m^\ast\)と書く。 これは掛け算について常に群になる。\(m\)が素数\(p\)なら\(0\)以外の全部なので\(\mathbb{Z}_p^\ast = \{1, 2, \dots, p-1\}\)で、要素数は\(p-1\)である。 たとえば\(\mathbb{Z}_5^\ast = \{1,2,3,4\}\)、\(\mathbb{Z}_{12}^\ast = \{1,5,7,11\}\)である。以後の章でもこの記法を使う。
例 4 が本シリーズの分岐点である. 素数を法にするか、合成数を法にするかで世界の性質が変わる。 素数なら割り算まで自由にできる豊かな世界、すなわち体になり、これが誤り訂正符号の舞台になる。
以下この節では、掛け算の群\(\mathbb{Z}_5^\ast\)と足し算の群\(\mathbb{Z}_8\)を例として使う。
部分群 — 群の中にある小さな群
群\(G\)の部分集合\(H\)が、\(G\)と同じ演算でそれ自身も群になっているとき、\(H\)を\(G\)の部分群という。 群の定義は 4 条件だが、条件 2 の結合律は\(G\)の演算がもともと満たしているので、\(G\)の要素だけを使う\(H\)では自動的に成り立つ。 したがって部分群かどうかは次の 3 つを確かめればよい。
| # | 条件 | 確かめること |
|---|---|---|
| 1 | 閉じている | \(h_1, h_2 \in H \Rightarrow h_1 \ast h_2 \in H\) |
| 2 | 単位元を含む | \(G\)の単位元\(e\)が\(H\)に入っている |
| 3 | 逆元を含む | \(h \in H \Rightarrow h^{-1} \in H\) |
例: 足し算の群\(\mathbb{Z}_8 = \{0,1,\dots,7\}\)、単位元は\(0\)。
- \(H = \{0, 4\}\)は部分群である。\(0+0=0\)、\(0+4=4\)、\(4+4=8\equiv0\)でどれも\(H\)の中にあり、閉じている。単位元\(0\)を含む。\(0\)の逆元は\(0\)、\(4\)の逆元は\(4\)で、どちらも\(H\)の中にある。
- \(H = \{0, 1\}\)は部分群でない。\(1+1 = 2\)が\(H\)に入っておらず、閉じていない。
- \(H = \{0, 1, 2\}\)も部分群でない。\(1+2=3\)が\(H\)に入っていない。\(3\)を足して\(\{0,1,2,3\}\)にしても\(2+3=5\)が入っておらず、閉じるまで要素を足していくと\(\mathbb{Z}_8\)全体になる。
\(\mathbb{Z}_8\)の部分群は\(\{0\}\)、\(\{0,4\}\)、\(\{0,2,4,6\}\)、\(\mathbb{Z}_8\)自身の 4 つしかない。要素数はそれぞれ\(1, 2, 4, 8\)で、どれも\(8\)の約数である。 これが偶然でないことを、この節の最後のラグランジュの定理で示す。
例: 掛け算の群\(\mathbb{Z}_5^\ast = \{1,2,3,4\}\)、単位元は\(1\)。\(H = \{1, 4\}\)は部分群である。\(4\cdot4 = 16\equiv1\)なので閉じており、\(1\)を含み、\(4\)の逆元は\(4\)自身である。
群の位数と巡回群
群\(G\)の要素の個数を群の位数といい\(|G|\)と書く。\(|\mathbb{Z}_8| = 8\)、\(|\mathbb{Z}_5^\ast| = 4\)である。
要素\(g\)を\(k\)個並べて演算したものを\(g^k\)と書く。演算が掛け算なら本当のべき乗であり、 演算が足し算なら\(g + g + \cdots + g = k \cdot g\)のことである。以下この章では、演算の種類によらずこの略記を使う。
\(g, g^2, g^3, \dots\)を作っていって\(G\)の全要素が現れるなら、\(g\)を生成元、\(G\)を巡回群という。
例: \(\mathbb{Z}_5^\ast\)で\(g = 2\)とすると
\(\{2,4,3,1\}\)と全要素が出た。よって\(2\)は生成元で、\(\mathbb{Z}_5^\ast\)は巡回群である。
要素の位数 — 単位元になるまでに要素を何個並べるか
群全体の位数とは別に、1 つの要素についても位数を定義する。
定義: 要素\(a\)を\(d\)個並べて演算した結果
が初めて単位元\(e\)になる最小の正整数\(d\)を\(a\)の位数という。演算が掛け算なら\(a^d = 1\)、 足し算なら\(d \cdot a = 0\)となる最小の\(d\)である。
\(d = 1\)は\(a\)を 1 個だけ置いた状態なので、位数\(1\)の要素は\(e\)自身だけである。
計算手順: \(a\)を 1 個、2 個、3 個、…と増やしながら値を書き、初めて\(e\)になったところの個数を読む。
例 A: 掛け算の群\(\mathbb{Z}_5^\ast\)、単位元は\(1\)
| \(a\) | 1 個 | 2 個 | 3 個 | 4 個 | 初めて 1 になる個数 = 位数 |
|---|---|---|---|---|---|
| \(2\) | \(2\) | \(2\cdot2=4\) | \(4\cdot2=8\equiv3\) | \(3\cdot2=6\equiv1\) | \(4\) |
| \(4\) | \(4\) | \(4\cdot4=16\equiv1\) | \(2\) | ||
| \(1\) | \(1\) | \(1\) |
例 B: 足し算の群\(\mathbb{Z}_8\)、単位元は\(0\)。各マスは\(a\)をその個数だけ足した合計で、8 以上なら 8 で割った余りを\(\equiv\)の右に書く。
| \(a\) | 1 個 | 2 個 | 3 個 | 4 個 | 5 個 | 6 個 | 7 個 | 8 個 | 初めて 0 になる個数 = 位数 |
|---|---|---|---|---|---|---|---|---|---|
| \(1\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | \(8\equiv0\) | \(8\) |
| \(2\) | 2 | 4 | 6 | \(8\equiv0\) | \(4\) | ||||
| \(3\) | 3 | 6 | \(9\equiv1\) | \(12\equiv4\) | \(15\equiv7\) | \(18\equiv2\) | \(21\equiv5\) | \(24\equiv0\) | \(8\) |
| \(4\) | 4 | \(8\equiv0\) | \(2\) | ||||||
| \(0\) | 0 | \(1\) |
位数\(d\)の要素\(a\)について、\(a, a^2, \dots, a^d\)の\(d\)個は互いに異なる。 理由は次のとおり。もし\(i < j \le d\)で\(a^i = a^j\)だったとすると、両辺に\(a^i\)の逆元を演算して\(a^{j-i} = e\)となる。 ところが\(j-i < d\)なので、\(d\)が\(e\)になる最小の個数であることに反する。
要素の位数が群の位数\(|G|\)に等しい要素が生成元である。 \(d = |G|\)なら、上の\(|G|\)個の異なる要素が群の全要素だからである。 例 B では\(1\)と\(3\)が位数\(8\)で生成元であり、位数\(4\)の\(2\)は\(\{2,4,6,0\}\)しか作れない。
これが後で効く場面. 生成元のべき乗で全要素を作れるという性質は、次の 2 か所でそのまま使われる。
要素が生成する部分群
位数\(d\)の要素\(a\)のべき乗をすべて集めた集合を
と書き、\(a\)が生成する部分群と呼ぶ。上で見たとおり要素数は\(d\)である。
方針: この集合が部分群だと分かれば、次のラグランジュの定理を当てはめて「要素の位数\(d\)は群の位数\(|G|\)を割り切る」が言える。それがこの節の最後の帰結につながる。 そのために、部分群の 3 条件を 1 つずつ確かめる。
- 閉じている。\(\langle a \rangle\)の 2 要素\(a^i, a^j\)を演算すると\(a^i \ast a^j = a^{i+j}\)である。\(i+j \le d\)ならこれは集合の中にある。 \(i+j > d\)なら\(a^{i+j} = a^d \ast a^{i+j-d} = e \ast a^{i+j-d} = a^{i+j-d}\)で、\(1 \le i+j-d \le d\)なのでやはり集合の中にある。
- 単位元を含む。\(e = a^d\)が集合の中にある。
- 逆元を含む。\(a^i \ast a^{d-i} = a^d = e\)なので\(a^i\)の逆元は\(a^{d-i}\)であり、これも集合の中にある。\(i = d\)のときは\(e\)の逆元が\(e\)自身である。
例: \(\mathbb{Z}_5^\ast\)の\(4\)は位数\(2\)で\(\langle 4 \rangle = \{4, 1\}\)である。これは部分群の例で確かめた\(\{1,4\}\)そのものである。 \(\mathbb{Z}_8\)の\(2\)は位数\(4\)で\(\langle 2 \rangle = \{2,4,6,0\}\)である。\(2+6 = 8\equiv 0\)、\(4+6=10\equiv2\)のように閉じており、\(0\)を含み、\(2\)と\(6\)、\(4\)と\(4\)が互いに逆元である。
ラグランジュの定理
ラグランジュの定理: 有限群\(G\)の部分群\(H\)の位数\(|H|\)は、\(|G|\)を割り切る。
つまり部分群の要素数は\(|G|\)の約数にしかなれない。\(\mathbb{Z}_8\)に要素数\(3\)や\(5\)の部分群が存在せず、 要素数\(1,2,4,8\)の 4 つしかなかったのはこのためである。
導出の方針: \(G\)全体を「\(H\)と同じ大きさの塊」に重なりなく切り分けられることを示す。塊の個数を\(k\)とすれば\(|G| = k \times |H|\)となり、\(|H|\)が\(|G|\)を割り切る。 以下 4 段階で示す。例として\(G = \mathbb{Z}_8\)、\(H = \{0,4\}\)を並走させる。
段階 1: 塊の作り方。\(G\)の要素\(g\)を 1 つ選び、\(H\)の各要素に\(g\)を演算したものを集めた集合を\(gH = \{g \ast h \mid h \in H\}\)と書く。\(H\)を\(g\)だけずらしたコピーである。 例では演算が足し算なので\(gH = \{g + h \mid h \in H\}\)であり、 \(0H = \{0, 4\}\)、\(1H = \{1, 5\}\)、\(2H = \{2, 6\}\)、\(3H = \{3, 7\}\)、\(4H = \{4, 8 \equiv 0\} = \{0,4\}\)、\(5H = \{5, 9 \equiv 1\} = \{1,5\}\)、…となる。
段階 2: どの塊も要素数はちょうど\(|H|\)。\(H\)の異なる 2 つの要素\(h_1 \ne h_2\)は、\(g\)を演算した後も異なる。 背理法で示す。仮に\(g \ast h_1 = g \ast h_2\)だったとすると、両辺の左から\(g^{-1}\)を演算して\(h_1 = h_2\)となり、\(h_1 \ne h_2\)と矛盾する。 よって\(H\)の\(|H|\)個の要素は\(gH\)の\(|H|\)個の互いに異なる要素に写り、\(gH\)の要素数は\(|H|\)である。例ではどの塊も 2 個である。
段階 3: 2 つの塊は「完全に同じ」か「共通要素なし」のどちらか。一部だけ重なることは起きない。 2 つの塊\(gH\)と\(g'H\)に共通の要素\(x\)が 1 個でもあったとする。\(x\)は\(gH\)の要素なので\(H\)のある要素\(h_1\)を使って\(x = g \ast h_1\)と書け、 同時に\(g'H\)の要素でもあるので\(H\)のある要素\(h_2\)を使って\(x = g' \ast h_2\)とも書ける。同じ\(x\)を 2 通りに書いただけなので
両辺の右から\(h_1^{-1}\)を演算すると\(g = g' \ast h_2 \ast h_1^{-1}\)である。これを\(gH\)の任意の要素\(g \ast h\)に代入すると
括弧の中は\(H\)の要素どうしの演算である。\(H\)は閉じていて逆元を含むので、括弧の中は\(H\)の要素である。よって\(g \ast h\)は\(g'H\)の要素であり、\(gH\)のすべての要素は\(g'H\)に含まれる。 \(g\)と\(g'\)の役割を入れ替えれば\(g'H\)のすべての要素も\(gH\)に含まれる。したがって\(gH = g'H\)である。 例では\(4H = \{0,4\}\)と\(0H = \{0,4\}\)は共通要素\(0\)を持ち、実際に完全に一致している。\(0H\)と\(1H\)は共通要素がない。
段階 4: すべての要素がどれかの塊に入る。\(e \in H\)なので\(g = g \ast e \in gH\)である。つまり\(g\)は自分の塊\(gH\)に入っている。
段階 3 と 4 から、\(G\)は互いに共通要素を持たない塊たちに完全に切り分けられる。同じ塊は 1 つと数える。段階 2 からどの塊も大きさは\(|H|\)である。塊の個数を\(k\)とすると\(|G| = k|H|\) ∎ 例では\(\mathbb{Z}_8\)が\(\{0,4\}, \{1,5\}, \{2,6\}, \{3,7\}\)の 4 塊に切り分けられ、\(8 = 4 \times 2\)である。
\(H\)が部分群でないと段階 3 が壊れる。 段階 3 で「括弧の中が\(H\)の要素」と言えたのは\(H\)が閉じているからである。 部分群でない\(H = \{0,1\}\)で同じ塊を作ると\(0H = \{0,1\}\)、\(1H = \{1,2\}\)となり、共通要素\(1\)を持つのに一致しない。 塊が中途半端に重なるので「同じ大きさの塊で重なりなく切り分ける」ことができず、\(|G| = k|H|\)は成り立たない。定理が部分群にしか適用できないのはこのためである。
帰結 — どの要素も |G| 個並べると単位元に戻る（後で使う重要事実）
本シリーズで実際に使うのは、ラグランジュの定理から出る次の帰結である。
帰結: 有限群\(G\)の任意の要素\(a\)について、\(a^{|G|} = e\)。
方針: \(a\)の位数\(d\)が\(|G|\)を割り切ることをラグランジュの定理から引き出し、\(|G| = dk\)と書く。すると\(a^{|G|}\)は\(a^d = e\)を\(k\)回掛けたものになり、\(e\)になる。
導出: \(a\)の位数を\(d\)とする。\(\langle a \rangle = \{a, \dots, a^d\}\)は要素数\(d\)の部分群であった。 ラグランジュの定理より\(d\)は\(|G|\)を割り切るので、整数\(k\)があって\(|G| = dk\)である。 \(a\)を\(dk\)個並べて演算するのは、「\(a\)を\(d\)個」のまとまりを\(k\)回繰り返すことなので
例: 掛け算。\(\mathbb{Z}_5^\ast\)は\(|G|=4\)である。\(a = 4\)は位数\(d = 2\)で、\(4 = 2 \times 2\)、\(4^4 = 4^2 \cdot 4^2 = 1 \cdot 1 = 1\)となる。 \(a = 2\)は位数\(d = 4 = |G|\)で、\(k = 1\)、\(2^4 \equiv 1\)は例 A の表のとおりである。
例: 足し算。\(\mathbb{Z}_8\)は\(|G|=8\)である。\(a = 2\)は位数\(d = 4\)で、\(8 = 4 \times 2\)。帰結は「\(2\)を 8 個足すと\(0\)」で、実際\(8 \cdot 2 = 16 \equiv 0\)である。
これがフェルマーの小定理の正体である. \(G = \mathbb{Z}_p^\ast\)は位数\(p-1\)なので、帰結をそのまま当てはめると
$$a^{p-1} \equiv 1 \pmod p$$
が出る。15 章で RSA を作るときの心臓部だが、その本質はこの群論の一般定理であり、数論の特別な魔法ではない。
2. 環 (Ring)
定義
集合\(R\)に足し算\(+\)と掛け算\(\times\)の 2 つの演算があり、次を満たすとき環という。
- \((R, +)\)が可換群である。単位元を\(0\)、\(a\)の逆元を\(-a\)と書く
- \(\times\)が結合律を満たし、単位元\(1\)を持つ
- 分配律\(a(b+c) = ab + ac\)、\((a+b)c = ac + bc\)が成り立つ
\(ab = ba\)が成り立てば可換環という。
条件 1 により引き算はいつでもできるが、掛け算の逆元は要求していないので、割り算ができない要素があってもよい。
例
- 整数全体\(\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 節の割り算の失敗はこれである。 方程式が解けず、因数分解も一意でなくなる。
次節の体は、この厄介ごとが起きない世界、つまり 0 以外のすべての要素が逆元を持つ環である。
3. 体 (Field)
定義
可換環\(F\)のうち、0 以外のすべての要素が掛け算の逆元を持つものを体という。
言い換えれば、四則演算が完全に自由にできる世界である。 演算そのものは環と同じく\(+\)と\(\times\)の 2 つであり、\(-\)と\(\div\)は 1 節で述べたとおり逆元との演算の略記である。 その 2 つが 0 除算を除いてどちらも打ち消せるので、\(+ - \times \div\)がいつでも実行でき、結果が必ず世界の中に留まる。
例
| 集合 | 体か | 理由 |
|---|---|---|
| 有理数\(\mathbb{Q}\)、実数\(\mathbb{R}\)、複素数\(\mathbb{C}\) | ✓ | おなじみの体。要素は無限個 |
| 整数\(\mathbb{Z}\) | ✗ | 2 の逆元が無い |
| \(\mathbb{Z}_p\)、\(p\)は素数 | ✓ | 有限体。次章の主役 |
| \(\mathbb{Z}_m\)、\(m\)は合成数 | ✗ | 零因子があり、逆元を持たない要素がある |
定理: \(\mathbb{Z}_m\)が体 \(\iff\) \(m\)が素数
方針: \(\mathbb{Z}_m\)が体であるための条件は「0 以外のすべての要素が掛け算の逆元を持つ」ことだけである。 逆元を持つ条件は 01 章で\(\gcd(a, m) = 1\)と分かっているので、「\(1 \le a \le m-1\)のすべてで\(\gcd(a,m)=1\)」と「\(m\)が素数」が同じことを示せばよい。両方向を別々に示す。
導出:
（\(\Leftarrow\)）\(m = p\)が素数なら、\(p\)の約数は 1 と\(p\)のみで\(a < p\)なので、\(1 \le a \le p-1\)のすべてで\(\gcd(a,p) = 1\)である。 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\)が合成数\(ab\)だと仮定し、「1 を\(a\)個足したもの」と「1 を\(b\)個足したもの」の積が 0 になることを導く。体には零因子が無いのでどちらかが 0 になるが、\(a, b\)は\(n\)より小さいので標数の最小性に反する。
導出: 標数\(n\)が合成数\(n = ab\)、\(1<a,b<n\)だとする。 体の中で\((\underbrace{1+\cdots+1}_{a})(\underbrace{1+\cdots+1}_{b})\)を分配律で展開すると、\(1 \times 1 = 1\)が\(ab\)個現れるので\(\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\)より\(-a = a\)、すなわち\(a\)の逆元は\(a\)自身である。したがって\(b\)を引くことは\(-b = b\)を足すことに等しく、足し算と引き算が同じという、実装上きわめて便利な性質が生まれる。 CRC（09 章）も AES（14 章）も、この性質の上に成り立っている。
4. GF(2) — 最小の体を作ってみる
\(p = 2\)として\(\mathbb{Z}_2 = \{0, 1\}\)を作る。これを\(\mathrm{GF}(2)\)と書く。GF は 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 そのものである。XOR は排他的論理和で、2 つのビットが異なるとき 1、同じとき 0 を返す。 乗法表は AND そのもので、両方 1 のときだけ 1 を返す。
XOR と AND は CPU が最も基本的な命令として 1 手で実行する演算なので、GF(2) の四則演算はそのまま 1 命令で実行できる。 ハードウェアで CRC（09 章）やパリティ検査（07 章）が高速に動くのは、この一致のおかげである。
さらに標数 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 つ | ✓ | ✓（0 以外） | \(\mathrm{GF}(p)\)（03 章）、\(\mathrm{GF}(2^m)\)（05 章） |
群の行の「—」は、演算が 1 つしかないので 2 つ目の演算について問う意味がないことを表す。
この先の道筋: