高校生のための有限体入門

476

はじめに

素数 $p$ に対して $F_{p} = {0, 1, 2, \dots, p - 1}$ とすると， $mod p$ での演算によって $F_{p}$ 内で和・差・積・（ $0$ でない元による）商を定義することができる．このように集合に四則演算が定まっている構造のことを，現代数学の言葉では「体」と呼ぶ．上述の $F_{p}$ の他に，有理数全体 $Q$ や実数全体 $R$ ，複素数全体 $C$ なども体の例である．
$F_{p}$ は $Q$ や $R$ と違って有限個（ $p$ 個）の元からなる．このような体を有限体という．実は $F_{p}$ の他にも，元の個数が素冪 $p^{n}$ であるような有限体 $F_{p^{n}}$ が存在するのだが，その構成法は $F_{p}$ に比べて少々難しいので，大学で数学を学んだ人以外にはあまり知られていないと思う．そこで本記事ではこれらの有限体 $F_{p^{n}}$ の構成法およびその使い道について解説する．

$F_{p}$ の代数閉包

有限体 $F_{p^{n}}$ は ${\overset{―}{F}}_{p}$ という大きな（有限体ではない）体から構成することができる．この体 ${\overset{―}{F}}_{p}$ は $F_{p}$ の代数閉包と呼ばれるものであり，大雑把に言えば $mod p$ の世界における複素数体 $C$ のようなものである．具体的には， ${\overset{―}{F}}_{p}$ は次のような性質を持っている：

$F_{p} \subset {\overset{―}{F}}_{p}$ .
任意の ${\overset{―}{F}}_{p}$ の元はある $F_{p}$ 係数多項式の根である．
任意の ${\overset{―}{F}}_{p}$ 係数多項式は $1$ 次式の積に因数分解できる．

${\overset{―}{F}}_{p}$ の具体的な構成法は少々難しく，またそれほど重要ではないので割愛する．以下の説明では上記の $3$ つの性質のみを用いる．

$F_{5}$ 係数の多項式 $x^{2} - 3$ は $F_{5}$ の中に根を持たないので， $F_{5}$ 係数の範囲ではこれ以上因数分解できないが， ${\overset{―}{F}}_{5}$ 係数の範囲では
$x^{2} - 3 = (x - α) (x - β) (α, β \in {\overset{―}{F}}_{p})$
と因数分解される．係数を比較すると $α + β = 0$ となるため， $α$ を $\sqrt{3}$ と書くことにすると $β = - \sqrt{3}$ と表せる．

${\overset{―}{F}}_{p}$ について考える上で重要なのが $p$ 乗写像
$F : {\overset{―}{F}}_{p} \to {\overset{―}{F}}_{p}; F (x) = x^{p}$
である．これをFrobenius写像という．明らかにFrobenius写像は積および商を保つが，実は和と差も保っている：

任意の $x, y \in {\overset{―}{F}}_{p}$ に対して $(x + y)^{p} = x^{p} + y^{p}$ および $(x - y)^{p} = x^{p} - y^{p}$ が成り立つ．

二項定理より
$(x + y)^{p} = \sum_{i = 0}^{p} (\binom{p}{i}) x^{i} y^{p - i}$
が成り立つ． $i = 1, 2, \dots, p - 1$ に対して $(\binom{p}{i})$ は $p$ の倍数なので $F_{p}$ において $0$ である．よって $(x + y)^{p} = x^{p} + y^{p}$ となる．
$((x - y) + y)^{p} = (x - y)^{p} + y^{p}$
を移項すれば $(x - y)^{p} = x^{p} - y^{p}$ も得られる．

Frobenius写像 $F : {\overset{―}{F}}_{p} \to {\overset{―}{F}}_{p}; F (x) = x^{p}$ は全単射である．

$a \in {\overset{―}{F}}_{p}$ に対して方程式 $x^{p} = a$ は ${\overset{―}{F}}_{p}$ 内に解を持つので $F$ は全射である．また
$y^{p} = z^{p} ⟹ (y - z)^{p} = 0 ⟹ y = z$
より $F$ は単射である．

任意の $x \in F_{p}$ に対して $x^{p} = x$ が成り立つというのがFermatの小定理であった．これは次のように一般化される：

任意の $x \in {\overset{―}{F}}_{p}$ に対し，ある正整数 $n$ が存在して $x^{p^{n}} = x$ となる．

$x$ はある $F_{p}$ 係数多項式の根なので
$x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0} = 0$
を満たす $a_{0}, a_{1}, \dots, a_{d - 1} \in F_{p}$ が存在する．この式より， $x^{i}$ の形の元は全て
$b_{d - 1} x^{d - 1} + \dots + b_{1} x + b_{0} (b_{0}, b_{1}, \dots, b_{d - 1} \in F_{p})$
と表せる．特に $S = {x, x^{p}, x^{p^{2}}, x^{p^{3}}, \dots}$ は有限集合である．写像 $F : S \to S; F (y) = y^{p}$ は単射なので全単射となる．特に $F^{n} (x) = x$ となる正整数 $n$ が存在するのでよい．

${\overset{―}{F}}_{p}$ の元 $x$ に対し， $x^{p^{n}} = x$ となる正整数 $n$ の最小値を $x$ の次数と呼ぶ．

Fermatの小定理より $F_{p}$ の元の次数は $1$ である．次数 $1$ の元は $x^{p} - x = 0$ の解なので高々 $p$ 個しか存在しない．よって $F_{p}$ は次数 $1$ の元全体に等しい．

${\overset{―}{F}}_{5}$ における $x^{2} - 3 = 0$ の解を $1$ つ取って $\sqrt{3}$ と書く．このとき
$\begin{aligned} {\sqrt{3}}^{5} = 9 \sqrt{3} = - \sqrt{3}, \\ {\sqrt{3}}^{25} = (- \sqrt{3})^{5} = \sqrt{3} \end{aligned}$
となる．つまり $\sqrt{3}$ の次数は $2$ である．

後で使うために， ${\overset{―}{F}}_{p}$ 係数の多項式の微分を定義しておく：

${\overset{―}{F}}_{p}$ 係数多項式 $f (x) = a_{d} x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0}$ に対して
$f^{'} (x) = d a_{d} x^{d - 1} + (d - 1) a_{d - 1} x^{d - 2} + \dots + a_{1}$
と定める．

${\overset{―}{F}}_{p}$ 係数多項式 $f (x), g (x)$ に対して $(f (x) g (x))^{'} = f^{'} (x) g (x) + f (x) g^{'} (x)$ が成り立つ．

展開することで $f (x) = a x^{d}, g (x) = b x^{e}$ の場合に帰着できる．この場合は容易である．

有限体の構成

素冪 $p^{n}$ に対し， $F_{p^{n}} = {x \in {\overset{―}{F}}_{p} ∣ x^{p^{n}} = x}$ と定める．つまり， $F_{p^{n}}$ は次数が $n$ の約数であるような ${\overset{―}{F}}_{p}$ の元全体からなる集合である．

Fermatの小定理より $F_{p} \subset F_{p^{n}}$ が成り立つ．また命題2より，任意の ${\overset{―}{F}}_{p}$ の元はある $F_{p^{n}}$ に含まれる．

$x, y \in F_{p^{n}}$ に対し， $x + y, x - y, x y \in F_{p^{n}}$ が成り立つ．さらに $y \neq 0$ ならば $x / y \in F_{p^{n}}$ も成り立つ．

命題1より $(x + y)^{p^{n}} = x^{p^{n}} + y^{p^{n}} = x + y$ となるので $x + y \in F_{p^{n}}$ である．残りの主張も同様に示される．

命題5より $F_{p^{n}}$ は体をなす．体 $F_{p^{n}}$ を位数 $p^{n}$ の有限体と呼ぶ．

$F_{p^{n}}$ の元の個数は $p^{n}$ である．

$F_{p^{n}}$ は方程式 $x^{p^{n}} - x = 0$ の ${\overset{―}{F}}_{p}$ における解全体である． ${\overset{―}{F}}_{p}$ 係数の範囲で
$x^{p^{n}} - x = \prod_{i = 1}^{p^{n}} (x - α_{i})$
と因数分解すると， $F_{p^{n}} = {α_{1}, \dots, α_{p^{n}}}$ である．よって $α_{1}, \dots, α_{p^{n}}$ が相異なることを示せばよい．上の式の両辺を微分すると， ${\overset{―}{F}}_{p}$ において $p^{n} = 0$ なので
$- 1 = \sum_{i = 1}^{p^{n}} \prod_{j \neq i} (x - α_{j})$
となる．この式に $x = α_{i}$ を代入すると
$\prod_{j \neq i} (α_{i} - α_{j}) = - 1$
となるので， $α_{1}, \dots, α_{p^{n}}$ が相異なることがわかる．

${\overset{―}{F}}_{5}$ における $x^{2} - 3 = 0$ の解を $1$ つ取って $\sqrt{3}$ と書くと，例3で見たように $\sqrt{3} \in F_{25}$ である．命題5より
$a + b \sqrt{3} (a, b \in F_{5})$
という形の元は全て $F_{25}$ に属する．またこれらの元は相異なることが容易に示せる． $F_{25}$ は $25$ 個の元からなるので，結局
$F_{25} = {a + b \sqrt{3} ∣ a, b \in F_{5}}$
となることがわかる．

有限体の包含関係

$F_{p^{n}} \subset F_{p^{m}} ⟺ n ∣ m$ .

$n ∣ m$ ならば $F_{p^{n}} \subset F_{p^{m}}$ であることは定義から明らかである．逆に $F_{p^{n}} \subset F_{p^{m}}$ であると仮定して $n ∣ m$ を示そう． $n$ を割り切る素冪 $l^{k}$ に対して $l^{k} ∣ m$ を示せばよいので， $n = l^{k}$ の場合に帰着される．命題6より， $F_{p^{l^{k}}}$ に含まれるが $F_{p^{l^{k - 1}}}$ に含まれない元 $x$ を取ることができる．このとき $x$ の次数はちょうど $l^{k}$ なので， $x \in F_{p^{m}}$ より $l^{k} ∣ m$ が得られる．

命題7より，小さい $n$ に対する $F_{p^{n}}$ の包含関係は以下のようになっている（矢印は包含写像）：
$F_{p^{4}} F_{p^{6}} F_{p^{2}} F_{p^{3}} F_{p^{5}} F_{p}$

次数の求め方

具体的な ${\overset{―}{F}}_{p}$ の元の次数を求めるには，以下の命題を用いるのが便利である：

$f (x)$ を $F_{p}$ 係数の $n$ 次多項式とし， $α$ を ${\overset{―}{F}}_{p}$ における $f (x)$ の根とする． $f (x)$ が $F_{p}$ 上既約（ $F_{p}$ 係数の範囲でこれ以上因数分解できない）ならば， $α$ の次数は $n$ であり， ${\overset{―}{F}}_{p}$ における $f (x)$ の根は $α, α^{p}, α^{p^{2}}, \dots, α^{p^{n - 1}}$ である．

$f (x) = a_{d} x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0} (a_{i} \in F_{p})$ とする． $β \in {\overset{―}{F}}_{p}$ が $f (x)$ の根ならば
$a_{d} β^{d} + a_{d - 1} β^{d - 1} + \dots + a_{1} β + a_{0} = 0$
であるが，両辺にFrobenius写像を適用すると， $a_{i}^{p} = a_{i}$ より
$a_{d} β^{d p} + a_{d - 1} β^{(d - 1) p} + \dots + a_{1}^{p} β + a_{0} = 0$
となるので， $β^{p}$ も $f (x)$ の根である．つまり， ${\overset{―}{F}}_{p}$ における $f (x)$ の根全体の集合を $S$ とすると，写像 $F : S \to S; F (x) = x^{p}$ が定まる． $F$ は単射なので全単射である． $F^{k} (α) = α$ となる正整数 $k$ のうち最小のものを取る． $T = {α, α^{p}, \dots, α^{p^{k - 1}}}$ と定めると， $F$ は全単射 $T \to T$ に制限できる．
$g (x) = a_{d} \prod_{β \in T} (x - β)$
と定めると， $g (x)$ の係数はFrobenius写像で不変なので， $g (x)$ は $F_{p}$ 係数多項式となる．定義より $g (x)$ は $f (x)$ を割り切るので， $f (x)$ が既約であるという仮定より $g (x) = f (x)$ となる．よって $k = n, T = S$ である．

Fibonacci数列への応用

有限体の応用例として，Fibonacci数の $mod p$ での振る舞いについて調べる．Fibonacci数列は
$F_{1} = F_{2} = 1, F_{n + 2} = F_{n + 1} + F_{n}$
により定まる数列であり，その一般項は
$F_{n} = \frac{ϕ^{n} - {\overset{―}{ϕ}}^{n}}{ϕ - \overset{―}{ϕ}} (ϕ = \frac{1 + \sqrt{5}}{2}, \overset{―}{ϕ} = \frac{1 - \sqrt{5}}{2})$
で与えられる．これの「 $mod p$ 版」を考えよう． ${\overset{―}{F}}_{p}$ における $x^{2} - 5 = 0$ の解を $1$ つ取って $\sqrt{5}$ と書く．

$p$ を素数とする．
(1) $p = 2$ ならば $\sqrt{5} = 1$ である．
(2) $p = 5$ ならば $\sqrt{5} = 0$ である．
(3) $p \equiv 1, 4 (\mod 5)$ ならば $\sqrt{5} \in F_{p}$ である．
(4) $p \equiv 2, 3 (\mod 5), p \neq 2$ ならば $\sqrt{5} \in F_{p^{2}} ∖ F_{p}$ であり， ${\sqrt{5}}^{p} = - \sqrt{5}$ である．

(1),(2)は明らかである．以下 $p$ は $2, 5$ でないとする．平方剰余の相互法則より， $p \equiv 1, 4 (\mod 5)$ ならば $p$ は $mod 5$ で平方剰余であり， $p \equiv 2, 3 (\mod 5)$ ならば $p$ は $mod 5$ で平方非剰余である．前者の場合， $x^{2} - 5 = 0$ は $F_{p}$ に解を持つので $\sqrt{5} \in F_{p}$ となる．後者の場合， $x^{2} - 5$ は $F_{p}$ 上既約なので，命題8より $\sqrt{5}$ の次数は $2$ であり， ${\sqrt{5}}^{p} = - \sqrt{5}$ となる．

以下では $p \neq 2, 5$ とする． ${\overset{―}{F}}_{p}$ の元 $α, β$ を
$α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2}$
により定める．また ${\overset{―}{F}}_{p}$ の元 $u_{n}$ を
$u_{n} = \frac{α^{n} - β^{n}}{α - β}$
により定める．すると $u_{1} = 1, u_{2} = α + β = 1$ であり，また $α^{n + 2} = α^{n + 1} + α^{n}$ および $β^{n + 2} = β^{n + 1} + β^{n}$ より
$u_{n + 2} = u_{n + 1} + u_{n}$
が成り立つ．すなわち， $u_{n}$ は $F_{n}$ を $mod p$ で考えたものに他ならない．これを用いると次のような事実が示せる．

素数 $p \neq 2, 5$ に対して $F_{n + 2 p} = F_{n + p} + F_{n} (\mod p)$ が成り立つ．

$α^{2} = α + 1$ にFrobenius写像を適用すると $α^{2 p} = α^{p} + 1$ となり， $α^{n + 2 p} = α^{n + p} + α^{n}$ が得られる．同様に $β^{n + 2 p} = β^{n + p} + β^{n}$ も成り立つので， $u_{n + 2 p} = u_{n + p} = u_{n}$ が得られる．

$p$ を $2, 5$ 以外の素数とする．
(1) $p \equiv 1, 4 (\mod 5)$ ならば $F_{n + p - 1} \equiv F_{n} (\mod p)$ が成り立つ．
(2) $p \equiv 2, 3 (\mod 5)$ ならば $F_{n + p + 1} \equiv - F_{n} (\mod p)$ が成り立つ．

$p \equiv 1, 4 (\mod 5)$ ならば命題9より $α, β \in F_{p}$ なので $α^{n + p - 1} = α^{n}, β^{n + p - 1} = β^{n}$ である．よって $u_{n + p - 1} = u_{n}$ が得られる． $p \equiv 2, 3 (\mod 5)$ ならば命題9より $α, β \in F_{p^{2}} ∖ F_{p}$ であり， $α^{p} = β, β^{p} = α$ である．よって
$α^{n + p + 1} = α^{n} (α β) = - α^{n}$
であり，同様に $β^{n + p + 1} = - β^{n}$ も成り立つので， $u_{n + p + 1} = - u_{n}$ が得られる．