Chapter 03

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

この章の位置づけ. 02 章で、\(\mathbb{Z}_p\)は\(p\)が素数のとき体になることを示した。 この章ではその体を具体的な数で動かし、逆元の公式、原始元、有限体上の連立方程式を扱う。 最後に、要素数が素数でない有限体が必要になる理由を述べ、次章以降につなぐ。

この章で使う既出の用語（定義は各リンク先）. \(a \bmod p\)と\(\equiv\)・\(\gcd\)・拡張ユークリッド・逆元の存在条件・繰り返し二乗法（01 章）、 群・単位元・逆元・\(\mathbb{Z}_p^\ast\)・群の位数と要素の位数・生成元・巡回群・フェルマーの小定理（02 章 1 節）、零因子（02 章 2 節）、 体・標数（02 章 3 節）。

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

この章を通じて\(p\)は素数を表す。\(\mathbb{Z}_p\)は体であり、これを\(\mathrm{GF}(p)\)と書く。 \(\mathbb{Z}_p\)の\(p\)は法だが、\(\mathrm{GF}(p)\)では次の 3 つの量がすべて\(p\)になる。

\(\mathrm{GF}\)の括弧の中は要素数を表す約束である。\(\mathrm{GF}(p)\)では三者が一致するが、5 節の\(\mathrm{GF}(p^m)\)では要素数と標数が異なる。 0 以外の要素がなす掛け算の群は\(\mathbb{Z}_p^\ast\)と書く。 Web 版ではこの見出しの下に、法を 2 から 17 まで変えて加法表と乗法表を表示する図がある。法が合成数のとき逆元を持たない要素があることが確かめられる。

GF(5) の演算表

加法表:

乗法表:

乗法表の各行は全要素の並べ替えになる

主張: \(a \neq 0\)を固定して\(a \times 1, a\times 2, \dots, a\times(p-1)\)を並べると、\(1, 2, \dots, p-1\)の並べ替えになる。

方針: \(p-1\)個の出力が互いに異なり、どれも 0 でないことを示す。候補は\(\{1,\dots,p-1\}\)の\(p-1\)個だけなので、全部が 1 回ずつ現れる。

導出: 異なる入力\(x \neq y\)は異なる出力\(ax \neq ay\)を与える。仮に\(ax = ay\)なら\(a^{-1}\)を掛けて\(x = y\)となり矛盾するからである。 出力はどれも 0 でない。体に零因子は無いので\(a \neq 0, x \neq 0 \Rightarrow ax \neq 0\)である。 \(p-1\)個の互いに異なる非零の出力が\(p-1\)個の候補\(\{1, \dots, p-1\}\)に収まるには、全部がちょうど 1 回ずつ現れるしかない ∎

各行に必ず 1 が現れるので、逆元は表から読める。\(2 \times 3 = 1\)より\(2^{-1} = 3\)、\(4\times 4 = 1\)より\(4^{-1} = 4\)である。

2. 逆元の公式

フェルマーの小定理\(a^{p-1} \equiv 1 \pmod p\)（\(a \neq 0\)）を\(a \cdot a^{p-2} \equiv 1\)と分けると

GF(5) で\(a=2\)なら\(2^{3} = 8 \equiv 3\)であり、乗法表の\(2^{-1}=3\)と一致する。

逆元の求め方は 2 つある。拡張ユークリッド（01 章）と、上の公式を繰り返し二乗法（01 章）で計算する方法である。 どちらも\(O(\log p)\)で、実装では前者が使われることが多い。

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

掛け算の群\(\mathbb{Z}_p^\ast\)の生成元を、有限体の文脈では原始元と呼ぶ。位数が\(p-1\)の要素、すなわちべき乗で全要素を巡る要素がこれにあたる。

原始元\(g\)があれば、\(0\)以外のどの要素\(y\)も\(y = g^x\)の形に書ける。この\(x\)を\(g\)を底とする\(y\)の離散対数という。 \(g^x\)は繰り返し二乗法で\(O(\log x)\)で計算できるが、\(y\)から\(x\)を求める効率のよい方法は知られていない。この非対称性がディフィー・ヘルマン鍵交換（17 章）の安全性の根拠である。 また原始元のべき乗は\(p-1\)個すべてを巡ってから 1 に戻るので、周期が最長になる。この性質を LFSR（13 章）とリード・ソロモン符号（11 章）で使う。

GF(7) で探す

\(3\)と\(5\)は 6 個すべてを出すので原始元である。\(2\)は位数\(3\)で\(\{2,4,1\}\)しか出ない。

原始元の個数

定理: 原始元が 1 つでも存在すれば、原始元はちょうど\(\varphi(p-1)\)個ある。 \(\varphi(p-1)\)はオイラー関数で、\(1\)以上\(p-1\)以下の整数のうち\(p-1\)と互いに素なものの個数である。\(1\)はどんな数とも互いに素なので\(\varphi(p-1) \ge 1\)である。 存在は05 章の定理 2 として述べる（証明は省略する）。

方針: 原始元\(g\)を 1 つ固定すると、0 以外の要素はすべて\(g^k\)と書ける。問いは「どの\(k\)で\(g^k\)が原始元になるか」に変わる。 \(g^k\)の位数を\(k\)の式で求めると\((p-1)/\gcd(k, p-1)\)になる。これが\(p-1\)に等しいのは\(\gcd(k,p-1) = 1\)のときに限り、そのような\(k\)の個数が\(\varphi(p-1)\)である。

導出: 例として\(p = 7\)、\(g = 3\)を並走させる。段階 1 で問いを言い換え、段階 2 と 3 で\(g^k\)の位数を求め、段階 4 で数える。

段階 1: すべての候補を\(g^k\)の形で書く。 \(g\)は原始元なので、0 以外の要素は\(g^1, g^2, \dots, g^{p-1}\)のどれかとして 1 回ずつ現れる。「原始元が何個あるか」は「\(g^k\)が原始元になる\(k\)が何個あるか」と同じ問いである。 例では\(3^1 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1\)で、6 個の要素が 1 回ずつ現れている。

段階 2: \(g^n = 1\)となる\(n\)は\(p-1\)の倍数に限る。 \(n\)を\(p-1\)で割って\(n = q(p-1) + r\)、\(0 \le r < p-1\)と書くと

\(0 < r < p-1\)なら\(g^r \neq 1\)である（\(g\)の位数が\(p-1\)だから）。よって

段階 3: \(g^k\)の位数は\((p-1)/\gcd(k, p-1)\)である。 \(g^k\)を\(j\)個掛けたものは\(g^{kj}\)である。段階 2 より\(g^{kj} = 1 \iff kj\)は\(p-1\)の倍数。位数はこの条件を満たす最小の正整数\(j\)である。

\(d = \gcd(k, p-1)\)とおき、\(k = dk'\)、\(p-1 = dt\)と書く。\(k'\)と\(t\)に共通の約数は 1 しかない。 条件「\(dk'j\)が\(dt\)の倍数」は、両方から\(d\)を落として「\(k'j\)が\(t\)の倍数」と書き換えられる。 \(k'\)と\(t\)は互いに素なので、\(k'j\)が\(t\)の倍数であれば\(j\)が\(t\)の倍数である。\(t\)を割り切る素因数は\(k'\)を割らないので\(j\)を割るしかないからである。

ここまでをまとめると

\(g^k\)を\(j\)個掛けて\(1\)になるのは\(j = t, 2t, 3t, \dots\)のときだけなので、位数は最小の\(t = (p-1)/\gcd(k, p-1)\)である。

例（\(p-1 = 6\)）:

\(2\)の位数が\(3\)になっていて、前の表で\(2\)のべき乗が\(\{2,4,1\}\)の 3 個で戻った事実と一致する。

段階 4: 数える。 原始元とは位数\(p-1\)の要素なので、段階 3 より\(\gcd(k, p-1) = 1\)と同値である。 \(1 \le k \le p-1\)で\(p-1\)と互いに素な\(k\)の個数が\(\varphi(p-1)\)である ∎

例では\(\gcd(k,6) = 1\)となる\(k\)は\(1, 5\)の 2 個なので\(\varphi(6) = 2\)であり、原始元は\(3^1 = 3\)と\(3^5 = 5\)の 2 個である。前の表で見つけた\(3, 5\)と一致する。

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

体の上では、実数と同じ手順で連立方程式が解ける。 掃き出し法は、1 本の式の係数を割って 1 にし、その式で他の式からその変数を消す操作を変数ごとに繰り返す。使う演算は四則演算だけなので、体の上ではそのまま実行できる。割り算は逆元の掛け算で行う。

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

手順 1: 1 本目の\(x\)の係数を 1 にする。\(2^{-1} = 3\)を両辺に掛ける。

手順 2: 2 本目から 1 本目を引いて\(x\)を消す。

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

手順 4: \(x + y = 3\)に代入して\(x = 0\)。

検算: \(2\cdot 0 + 3\cdot 3 = 9 \equiv 4\)、\(0 + 3 = 3\)。

途中に分数が現れず、すべて\(\{0,1,2,3,4\}\)の中で完結している。 リード・ソロモン符号（11 章）では、壊れた位置を未知数、シンドロームを右辺とする有限体上の連立方程式をこの手順で解く。

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

コンピュータは 1 バイトを\(2^8 = 256\)通りの値として扱う。256 は素数ではないので\(\mathbb{Z}_{256}\)は体にならず、素数 251 を使うと 5 つの値が無駄になってバイト境界とずれる。 体にならないのは整数の剰余\(\mathbb{Z}_{256}\)として作った場合であって、要素数 256 の体が存在しないわけではない。

1 節の約束どおり、\(\mathrm{GF}\)の括弧の中は要素数である。要素数\(p^m\)の体を\(\mathrm{GF}(p^m)\)と書く。\(m = 1\)のときが 1 節の\(\mathrm{GF}(p) = \mathbb{Z}_p\)である。 \(m \ge 2\)のとき\(\mathrm{GF}(p^m)\)は整数の剰余ではないので法に当たる数はなく、\(\mathbb{Z}_{p^m}\)とは別物である。\(\mathbb{Z}_4\)は体でないが、要素数 4 の体は別に存在し、それが\(\mathrm{GF}(2^2) = \mathrm{GF}(4)\)である。 その標数は\(p^m\)ではなく\(p\)である。これは次の定理の証明の段階 1 で分かる。

定理: 有限体\(F\)の標数を\(p\)とすると、\(F\)の要素数は\(p^m\)の形である。逆に、任意の素数\(p\)と正整数\(m\)に対して要素数\(p^m\)の体が存在する。 02 章の定理より有限体の標数は素数なので、この\(p\)も素数であり、1 節の\(\mathrm{GF}(p)\)が定まる。\(\mathrm{GF}(p)\)自身は標数\(p\)、要素数\(p = p^1\)で、定理の\(m=1\)の場合である。

定理の意味: 標数が\(p\)であることは、\(1\)を足し続ける列\(0, 1, 1+1, \dots\)が\(p\)個で一巡することしか言っていない。 \(F\)にはこの列に現れない要素があってよく、たとえば要素数 256 の体なら、\(1\)から足し算だけで作れるのは\(0\)と\(1\)の 2 個で、残り 254 個は別の要素である。 定理は、そうした要素を全部含めた\(F\)全体の個数に制限を付ける。標数が\(2\)なら全体は\(2, 4, 8, 16, \dots\)のどれかであり、要素数\(6\)や\(12\)の体は存在しない。 「標数は素数」だけからはこの制限は出てこないので、証明が要る。

例: GF(4)

証明の例として\(\mathrm{GF}(4) = \{0, 1, \alpha, \beta\}\)を使う。\(\mathrm{GF}(4)\)は 4 が素数でないので整数の剰余では作れず、\(0, 1\)以外の要素には整数の名前が付かない。\(\alpha\)と\(\beta\)は変数ではなく、下の演算表で振る舞いが完全に決まる具体的な要素である。正体は05 章で明かす。

\(1 + 1 = 0\)なので標数は\(2\)である。要素数は\(4 = 2^2\)であり、標数\(2\)とは異なる。\(\mathrm{GF}(4)\)の括弧の中の 4 は要素数であって、標数でも法でもない。

前半の証明: 要素数は\(p^m\)

方針: \(F\)の中に\(\mathrm{GF}(p)\)と同じ演算表を持つ\(p\)個の要素があることを示し、その集合を\(P\)と書く。 次に\(F\)の要素\(b_1, b_2, \dots\)を順に選んで固定し、\(c_1 b_1 + c_2 b_2 + \cdots\)で得られる値をすべて集めた集合を\(S\)とする。ここで\(b_j\)は各段階で固定する定数、\(c_j\)は\(P\)上を動く変数である。各\(c_j\)が\(p\)通りなので、\(b\)を 1 つ増やすたびに\(S\)の要素数は\(p\)倍になる。\(S = F\)となったとき\(|F| = p^m\)が従う。

\(F\)の標数は\(p\)なので、\(F\)の中で\(1\)を\(0\)回から\(p-1\)回まで足した\(p\)個の要素は\(\mathrm{GF}(p)\)と同じ演算規則に従う。この\(p\)個の集合を\(P\)と書く。例では\(P = \{0, 1\}\)であり、\(\mathrm{GF}(2)\)そのものである。

\(F\)の 0 でない要素\(b_1\)を 1 つ取り、\(S_1 = \{c_1 b_1 \mid c_1 \in P\}\)とおく。 \(c_1 b_1 = c_1' b_1\)なら\(b_1^{-1}\)を掛けて\(c_1 = c_1'\)なので、\(S_1\)は\(p\)個の異なる要素からなる。 \(S_1 = F\)ならここで終わりで、要素数は\(p\)である。 例では\(b_1 = 1\)と取ると\(S_1 = \{0\cdot 1, 1\cdot 1\} = \{0, 1\}\)で、\(\alpha\)と\(\beta\)が入っていないので終わらない。

そうでなければ\(S_1\)に入らない要素\(b_2\)を取り、\(S_2 = \{c_1 b_1 + c_2 b_2 \mid c_1, c_2 \in P\}\)とおく。 例では\(b_2 = \alpha\)と取ると、係数\((c_1, c_2)\)の 4 通りに対して

となり、\(S_2 = \{0, 1, \alpha, \beta\} = F\)である。4 個がすべて異なる要素になっている。

一般に、\(c_1\)と\(c_2\)はそれぞれ独立に\(P\)の\(p\)個の値を取るので、組\((c_1, c_2)\)は\(p \times p = p^2\)通りある。異なる組が異なる値を与えることを示せば\(S_2\)は\(p^2\)個の異なる要素からなる。もし\(c_2 \neq c_2'\)で

が成り立つなら、\(b_2\)の項を左辺にまとめて\(b_2\)について解くと

となる。右辺は「\(P\)の要素 \(\times\, b_1\)」の形なので\(S_1\)の要素だが、\(b_2\)は\(S_1\)の外から取ったので矛盾する。よって\(c_2 = c_2'\)であり、すると\(c_1 b_1 = c_1' b_1\)から\(c_1 = c_1'\)である。 例で言えば、\(1\cdot 1 + 1\cdot\alpha = 0\cdot 1 + 0\cdot\alpha\)が成り立つとすると、\((1-0)\alpha = (0-1)\cdot 1\)より\(\alpha = -1 = 1\)（標数 2 なので\(-1 = 1\)）となるが、\(\alpha\)は\(S_1 = \{0,1\}\)の外から取ったので矛盾する。

同じ手順を繰り返す。\(S_i \neq F\)である限り\(S_i\)に入らない\(b_{i+1}\)を取り、

とおく。各\(c_j\)は\(P\)の\(p\)個の値を独立に取るので、組\((c_1, \dots, c_{i+1})\)は\(p^{i+1}\)通りある。\(S_2\)と同じ議論で異なる組は異なる値を与えるので、\(|S_{i+1}| = p^{i+1}\)である。 \(F\)は有限なのでこの手順はどこかで止まり、止まったときの\(S_m\)が\(F\)全体である。よって\(F\)の要素数は\(p^m\)である ∎ 例では\(m = 2\)で止まり、要素数は\(2^2 = 4\)である。要素数 256 の体（標数 2）なら\(P = \{0, 1\}\)で、\(b_1, \dots, b_8\)の 8 個を取る。各\(c_j\)が 0 か 1 なので\(2^8 = 256\)通りの組で\(F\)全体を尽くし、係数の並び\((c_1, \dots, c_8)\)が 8 ビット、つまり 1 バイトに対応する。

後半と次章への接続

後半、すなわち任意の\(p^m\)に対して体が存在することについては、05 章で\(p = 2\)の場合の作り方を示す。 \(\mathrm{GF}(p)\)が整数を素数で割った余りの世界であったのに対し、\(\mathrm{GF}(p^m)\)は多項式を既約多項式で割った余りの世界として作る。 同じ論法を整数の代わりに多項式に適用するために、次章で多項式の世界を整備する。

6. まとめ