Chapter 03

有限体 GF(p) — 素数個の要素で作る完全な世界

この章の位置づけ. 02 章で「\(\mathbb{Z}_p\)は\(p\)が素数のとき体になる」と分かった。 この章ではその世界を実際に手で触って、後の章で使う具体的な道具を揃える。

特に重要なのは次の 3 つ:

• フェルマーの小定理 — RSA の心臓部（16 章）
• 原始元（生成元） — 離散対数暗号と LFSR の心臓部（13・17 章）
• 有限体上の連立方程式 — 誤り訂正の心臓部（11 章）

どれも「有限なのに四則演算が完備」という性質から自然に出てくる。

1. GF(p) の構成と演算表

定義: 素数\(p\)に対し、\(\mathrm{GF}(p) = \{0, 1, 2, \dots, p-1\}\)に\(\bmod p\)の加減乗除を入れたもの。 （\(\mathbb{F}_p\)とも書く。GF は Galois Field = ガロア体。）

実例: GF(5) の演算表

加法表（\(\bmod 5\)）:

乗法表:

乗法表の読み方——ここに体の秘密が見える. 0 の行を除いた各行を見てほしい。どの行にも 1〜4 が過不足なく 1 回ずつ現れている。

これは偶然ではない。\(a \neq 0\)を固定して\(a \times 1, a\times 2, \dots, a\times(p-1)\)を並べると、 必ず全要素の並べ替えになる（なぜか: もし\(ax = ay\)なら\(a^{-1}\)を掛けて\(x=y\)。 つまり異なる入力は必ず異なる出力になる。有限集合から同じ有限集合への単射は全射）。

各行に必ず 1 が現れる = すべての要素が逆元を持つ。乗法表そのものが体の証明になっている。

逆元は表から直接読める: \(2 \times 3 = 1\)なので\(2^{-1} = 3\)、\(4\times 4 = 1\)なので\(4^{-1} = 4\)。

逆元の 2 つの求め方

方法 1: 拡張ユークリッド（01 章）— \(O(\log p)\)で高速。実装ではこちら。

方法 2: フェルマーの小定理（次節）— \(a^{-1} = a^{p-2} \bmod p\)。数式が簡潔で、体の構造を使う。

2. フェルマーの小定理

定理

\(p\)が素数で\(a\)が\(p\)の倍数でないとき:

導出 1（群論から — 02 章の一般定理の特別な場合）

\(\mathrm{GF}(p)\)の 0 以外の要素は、掛け算について群\(\mathbb{Z}_p^\ast\)をなす（位数\(p-1\)）。 02 章のラグランジュの定理より、任意の要素\(a\)について\(a^{|G|} = a^{p-1} = 1\) ∎

導出 2（並べ替えによる — 具体的で分かりやすい）

上の乗法表の観察を使う。\(a \neq 0\)を固定すると

（並び順は違うが集合としては同じ。理由は上のコラムの通り。） 両辺の全要素を掛け合わせる:

\((p-1)!\)は\(p\)と互いに素（\(p\)は素数で、\(1\)から\(p-1\)のどれも\(p\)で割れない）なので逆元を持つ。 両辺に\(((p-1)!)^{-1}\)を掛けて:

系: 逆元の公式

\(a^{p-1} = a \cdot a^{p-2} \equiv 1\)より

実例（GF(5)、\(a=2\)）: \(2^{5-2} = 2^3 = 8 \equiv 3 \pmod 5\)。乗法表の\(2^{-1}=3\)と一致 ✓

3. 原始元（生成元）と離散対数

定義

\(g \in \mathrm{GF}(p)^\ast\)のべき乗\(g^1, g^2, \dots, g^{p-1}\)が\(\{1,2,\dots,p-1\}\)をすべて尽くすとき、 \(g\)を原始元（primitive element / 生成元）という。

実例: GF(7) で探す

\(3\)と\(5\)が原始元。\(2\)は違う（\(\{1,2,4\}\)しか作れない）。

なぜ原始元が重要なのか——2 つの応用.

① 離散対数問題（暗号） 原始元\(g\)があれば、\(0\)以外のどの要素\(y\)も必ず\(y = g^x\)の形に書ける。 この\(x\)を離散対数という。 ここで決定的なのは、\(g^x\)の計算は速いのに、\(y\)から\(x\)を求めるのは絶望的に遅いという非対称性。

• \(g^x \bmod p\): 繰り返し二乗法で\(O(\log x)\)——一瞬
• \(y\)から\(x\): 現在知られている最良の方法でも\(p\)が大きいと天文学的時間

この「行きは楽、帰りは地獄」がディフィー・ヘルマン鍵交換（17 章）の安全性の正体である。

② 最長周期の生成（誤り訂正・乱数） 原始元のべき乗は\(p-1\)個すべてを巡ってから 1 に戻る。 つまり取りうる限り最長の周期を持つ。 この性質が LFSR（13 章）の M 系列や、リード・ソロモン符号（11 章）の設計に直接使われる。

原始元の個数

定理: \(\mathrm{GF}(p)\)の原始元は\(\varphi(p-1)\)個ある（\(\varphi\)はオイラー関数、15 章）。

\(p=7\)なら\(\varphi(6) = \varphi(2\cdot3) = 1\cdot 2 = 2\)個。上の表と一致 ✓

4. GF(p) 上の線形代数 — 誤り訂正の道具

体の上では、実数とまったく同じ手順で連立方程式が解ける。 掃き出し法（ガウスの消去法）が使えるのは、割り算が自由にできるからである。

実例: GF(5) で連立方程式を解く

手順 1: 1 本目を\(x\)の係数 1 に正規化する. 実数なら「両辺を 2 で割る」ところだが、有限体では逆元を掛ける。 乗法表より\(2^{-1} = 3\)なので、1 本目の両辺に 3 を掛ける:

（\(6 \equiv 1\)、\(9 \equiv 4\)、\(12 \equiv 2\)）

手順 2: 2 本目から\(x\)を消去する.

（\(-3 \equiv 2 \pmod 5\)）

手順 3: \(y\)を求める. 両辺に\(2^{-1} = 3\)を掛けて:

手順 4: 代入して\(x\)を求める. 2 本目\(x + y = 3\)に\(y=3\)を入れて\(x = 0\)。

検算: \(2\cdot 0 + 3\cdot 3 = 9 \equiv 4 \pmod 5\) ✓ ／ \(0 + 3 = 3\) ✓

注目すべき点. 手順はすべて実数のときの掃き出し法と同一である。 唯一の違いは「割り算」が「逆元を掛ける」に変わっただけ。 しかも途中に分数が一度も現れず、すべて\(\{0,1,2,3,4\}\)の中で完結している。 有限体が「有限なのに完全」というのはこういうことである。

これが誤り訂正でどう使われるか. リード・ソロモン符号（11 章）では、「受信データのどこが壊れたか」を突き止めるために 有限体上の連立方程式を解く。壊れた位置が未知数で、シンドロームが右辺になる。 実数の世界と同じ手順で解けるのは、有限体が体だから—— つまり02 章で「割り算ができる」ことにこだわった理由がここで回収される。

5. GF(p) の限界 — なぜ次章が必要か

\(\mathrm{GF}(p)\)は美しいが、実装上は不便な点がある。

コンピュータは 2 進数で動く。1 バイト = 8 ビット = 256 通りの値を扱いたい。 ところが256 は素数ではない（\(256 = 2^8\)）。 \(\mathrm{GF}(256)\)を\(\mathbb{Z}_{256}\)として作ろうとしても、02 章の定理により体にならない （\(2 \times 128 = 256 \equiv 0\)という零因子が存在する）。

かといって\(\mathrm{GF}(251)\)（251 は素数）を使うと、 256 通りの値のうち 5 つが無駄になり、バイト境界とずれて扱いにくい。

解決の方針（04〜05 章）. 「要素数が素数でなければ体にならない」というのは間違いである。正しくは:

有限体の要素数は必ず素数のべき\(p^m\)であり、逆に任意の\(p^m\)に対して体が存在する。

つまり\(\mathrm{GF}(2^8) = \mathrm{GF}(256)\)は存在する。 ただし\(\mathbb{Z}_{256}\)（整数の\(\bmod 256\)）とは別物として作る必要がある。

作り方の見取り図はこうである:

• \(\mathbb{Z}\)を素数\(p\)で割った余りの世界\(\to\) \(\mathrm{GF}(p)\)（この章）
• 多項式を既約多項式で割った余りの世界\(\to\) \(\mathrm{GF}(p^m)\)（05 章）

まったく同じ論法を、整数の代わりに多項式に対して適用するだけ。 そのために次章で多項式の世界を整備する。

6. まとめ