第11章有限体（代数学（群・環・体）） | Lemma

この章の目標

$\mathbb{F}_{16}$ などで具体的に計算でき、 $x^{q^n} - x$ の既約分解から既約多項式・原始多項式の個数を求められる

トレースとノルムの全射性とヒルベルトの定理 90 を、有限体の場合に証明できる

有限体上の多項式の因数分解アルゴリズム（無平方分解・次数別分解・カントール–ザッセンハウス法）の正しさを説明できる

シュヴァレー–ワーニングの定理を証明し、有限体上の二次曲線の点を数えられる

CRC・AES・リード–ソロモン符号で有限体がどう使われるかを説明できる

前提：第8章（有限体の基本定理）、第9章（有限体のガロア群）。11.9 節では第1章のルジャンドル記号を使う。

第8章で、有限体は元の個数 $q = p^n$ で決まり、乗法群は巡回群であることを示した。第9章では、そのガロア群がフロベニウス写像で生成される巡回群であることを見た。本章ではこれらを道具として、有限体の上で具体的に計算する方法を整える。既約多項式はいくつあるか、多項式をどう因数分解するか、方程式の解はいくつあるか、といった問いに、有限体ではきれいな答えがある。

有限体は計算機の中で最もよく使われる体でもある。誤り検出の CRC、共通鍵暗号 AES、リード–ソロモン符号、楕円曲線暗号は、いずれも有限体の算術の上に作られている。最後の節でそれらへの橋渡しをする。

本章では $p$ は素数、 $q$ は $p$ のべきとし、 $\operatorname{Fr}_q(a) = a^q$ と書く。

11.1 有限体の復習と具体的な構成

第8章・第9章の結果をまとめておく。

元の個数が $q$ の体 $\mathbb{F}_q$ は $x^q - x$ の分解体として同型を除いて一意に存在し、 $\mathbb{F}_{p^n}$ が $\mathbb{F}_{p^m}$ を含む $\iff$ $m \mid n$ （第8章定理 8.41）。 $\mathbb{F}_q^\times$ は位数 $q - 1$ の巡回群（第8章定理 8.40）。
$\mathbb{F}_{q^n}/\mathbb{F}_q$ はガロア拡大で、ガロア群は $\operatorname{Fr}_q$ で生成される位数 $n$ の巡回群（第9章定理 9.14 とその後の注意）。 $\mathbb{F}_q$ 上の既約多項式の根の 1 つを $\alpha$ とすると、根全体は $\alpha, \alpha^q, \alpha^{q^2}, \dots$ である（第9章例 9.15(2) と同様）。

$\mathbb{F}_{q^n}$ を具体的に作るには、 $\mathbb{F}_q$ 上の $n$ 次既約多項式 $f$ をとって $\mathbb{F}_q[x]/(f)$ を考えればよい（第8章定理 8.8）。元は $n - 1$ 次以下の多項式で表され、和は係数ごと、積は $f$ で割った余りである。

例 11.1

$\mathbb{F}_4 = \mathbb{F}_2[x]/(x^2 + x + 1) = \lbrace 0, 1, \omega, \omega^2 = \omega + 1 \rbrace$ （第8章例 8.22）と $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$ （例 8.42(1)）は第8章で見た。 $\mathbb{F}_9 = \mathbb{F}_3[x]/(x^2 + 1) = \mathbb{F}_3(i)$ では、 $1 + i$ のべきが $1, 1 + i, 2i, 1 + 2i, 2, 2 + 2i, i, 2 + i$ と $\mathbb{F}_9^\times$ を一巡する（例 8.42(2)）。
$\mathbb{F}_{16} = \mathbb{F}_2[x]/(x^4 + x + 1)$ （既約性は第6章例 6.28(2)）。 $\alpha = \overline{x}$ とすると $\alpha^4 = \alpha + 1$ 。 $\alpha^k$ を $\alpha^3, \alpha^2, \alpha, 1$ の係数を並べた 4 桁の 2 進数で表すと次のようになる。 $\alpha^3 \neq 1$ , $\alpha^5 \neq 1$ なので $\alpha$ の位数は 15 で、 $\alpha$ は $\mathbb{F}_{16}^\times$ の生成元である。

$k$	0	1	2	3	4	5	6	7
$\alpha^k$	0001	0010	0100	1000	0011	0110	1100	1011
$k$	8	9	10	11	12	13	14
$\alpha^k$	0101	1010	0111	1110	1111	1101	1001

たとえば $\alpha^3 + \alpha + 1 = \alpha^7$ なので $(\alpha^3 + \alpha + 1)^{-1} = \alpha^8 = \alpha^2 + 1$ 。部分体 $\mathbb{F}_4$ は $a^4 = a$ をみたす元全体 $\lbrace 0, 1, \alpha^5, \alpha^{10} \rbrace$ で、 $\omega = \alpha^5 = \alpha^2 + \alpha$ は $\omega^2 + \omega + 1 = 0$ をみたす。

11.2 $x^{q^n} - x$ の分解と既約多項式の個数

定理 11.2 $\mathbb{F}_q[x]$ において、 $x^{q^n} - x$ は、次数が $n$ の約数であるモニックな既約多項式すべての（1 回ずつの）積である。

証明. $(x^{q^n} - x)' = -1$ なので $x^{q^n} - x$ は重根をもたず（第8章命題 8.36）、相異なるモニック既約多項式の積である。 $f$ を $d$ 次のモニック既約多項式、 $E = \mathbb{F}_q[x]/(f) = \mathbb{F}_q(\alpha)$ （ $\alpha = \overline{x}$ ）とすると、 $f$ は $\alpha$ の最小多項式なので、 $f \mid x^{q^n} - x$ $\iff$ $\operatorname{Fr}_q^n(\alpha) = \alpha$ $\iff$ $\operatorname{Fr}_q^n = \mathrm{id}_E$ （自己同型は $\alpha$ の像で決まる） $\iff$ $d \mid n$ （ $\operatorname{Gal}(E/\mathbb{F}_q)$ は $\operatorname{Fr}_q$ で生成される位数 $d$ の巡回群）。 $\square$

$d$ 次のモニック既約多項式の個数を $N_q(d)$ とし、次数を比べると

q^n = \sum_{d \mid n} dN_q(d) \tag{1}

これを $N_q(n)$ について解く。メビウス関数 (Möbius function) $\mu$ を、 $\mu(1) = 1$ 、 $n$ が相異なる $k$ 個の素数の積なら $\mu(n) = (-1)^k$ 、 $n$ がある素数の平方で割り切れるなら $\mu(n) = 0$ と定める。 $n > 1$ なら $\sum_{d \mid n}\mu(d) = 0$ である（ $n$ の相異なる素因数を $k \geq 1$ 個とすると、和は $\sum_j \binom{k}{j}(-1)^j = (1 - 1)^k$ ）。

定理 11.3（メビウスの反転公式, Möbius inversion formula） $F, G\colon \mathbb{N} \to \mathbb{Z}$ がすべての $n$ で $F(n) = \sum_{d \mid n} G(d)$ をみたせば、 $G(n) = \sum_{d \mid n}\mu(d)F(n/d)$ 。

証明. $de \mid n$ となる組 $(d, e)$ についての和の順序を入れかえると $\sum_{d \mid n}\mu(d)\sum_{e \mid n/d}G(e) = \sum_{e \mid n}G(e)\sum_{d \mid n/e}\mu(d)$ で、内側の和は $e = n$ のとき $1$ 、それ以外は $0$ 。 $\square$

系 11.4（ガウスの公式） $N_q(n) = \dfrac{1}{n}\sum_{d \mid n}\mu(d)q^{n/d}$ 。また $1 \leq N_q(n) \leq q^n/n$ 。

証明. (1) に定理 11.3 を $F(n) = q^n$ , $G(d) = dN_q(d)$ として使う。上からの評価は (1) から、 $N_q(n) \geq 1$ は $\mathbb{F}_{q^n}^\times$ の生成元の最小多項式が $n$ 次であることからわかる。 $\square$

$q = 2$ では次のようになる（ $n \leq 8$ のすべての多項式を調べ尽くす計算でも確かめた。3 行目は定理 11.6）。

$n$	1	2	3	4	5	6	7	8
$N_2(n)$	2	1	2	3	6	9	18	30
原始多項式の個数	1	1	2	2	6	6	18	16

たとえば $N_2(8) = (2^8 - 2^4)/8 = 30$ , $N_2(6) = (2^6 - 2^3 - 2^2 + 2)/6 = 9$ 。 $N_q(n) \approx q^n/n$ （問題 11.5）なので、 $n$ 次のモニック多項式をランダムに選ぶとおよそ $1/n$ の確率で既約である。既約多項式を探すアルゴリズムはこれに基づく。

11.3 原始元と原始多項式

定義 11.5（原始元・原始多項式） $\mathbb{F}_{q^n}^\times$ の生成元を $\mathbb{F}_{q^n}$ の原始元 (primitive element) といい、その $\mathbb{F}_q$ 上の最小多項式を原始多項式 (primitive polynomial) という。

注意

同じ名前で別の概念を指すので注意する。第8章定理 8.43 の「原始元」は $L = K(\gamma)$ となる $\gamma$ のことで、上の意味の原始元はそれより強い条件である（例 11.8 の $x^4 + x^3 + x^2 + x + 1$ の根は、前者の意味では $\mathbb{F}_{16}/\mathbb{F}_2$ の原始元だが、後者の意味では原始元でない）。第6章定義 6.17 の「原始多項式」は係数の最大公約数（内容）が単元である多項式のことで、体上の $0$ でない多項式はすべてこの意味で原始的なので、本章では定義 11.5 の意味でだけ使う。なお $\mathbb{F}_p$ の原始元とは、法 $p$ の原始根（第1章定義 1.41）のことである。

定理 11.6 $\mathbb{F}_{q^n}$ の原始元はちょうど $\varphi(q^n - 1)$ 個あり、 $\mathbb{F}_q$ 上の $n$ 次の原始多項式はちょうど $\varphi(q^n - 1)/n$ 個ある。

証明. 前半は位数 $q^n - 1$ の巡回群の生成元の個数である（第2章系 2.25）。原始元 $\gamma$ のべきは $\mathbb{F}_{q^n}^\times$ を尽くすので $\mathbb{F}_q(\gamma) = \mathbb{F}_{q^n}$ で、最小多項式は $n$ 次、その根は相異なる $n$ 個の $\gamma^{q^i}$ （ $0 \leq i < n$ ）である（第9章例 9.15(2) と同様）。これらは自己同型 $\operatorname{Fr}_q^i$ による像なので位数は $\gamma$ と等しく、すべて原始元である。よって原始元全体は各原始多項式の根 $n$ 個ずつに分かれる。 $\square$

命題 11.7 $f \in \mathbb{F}_q[x]$ を $n$ 次のモニック既約多項式（ $f \neq x$ ）とする。 $f$ が原始多項式 $\iff$ $q^n - 1$ の各素因数 $\ell$ について $x^{(q^n-1)/\ell} \not\equiv 1 \pmod f$ 。

証明. $f$ の根はすべて同じ位数をもつので、 $f$ が原始的 $\iff$ $\overline{x} \in (\mathbb{F}_q[x]/(f))^\times \cong \mathbb{F}_{q^n}^\times$ の位数が $q^n - 1$ 。その位数は $q^n - 1$ を割り、 $q^n - 1$ でなければある $(q^n - 1)/\ell$ を割る。 $\square$

例 11.8 $q = 2$ , $n = 4$ の原始多項式は $\varphi(15)/4 = 2$ 個で、 $x^4 + x + 1$ と $x^4 + x^3 + 1$ 。 $x^4 + x^3 + x^2 + x + 1$ も既約だが、 $(x - 1)(x^4 + x^3 + x^2 + x + 1) = x^5 - 1$ よりその根の位数は 5 で、原始的でない。 $n = 8$ では既約多項式 30 個のうち $\varphi(255)/8 = 16$ 個が原始的である。 $2^n - 1$ が素数（ $n = 2, 3, 5, 7$ など）なら、 $\mathbb{F}_2$ に属さない元の位数はすべて $2^n - 1$ なので、 $n$ 次既約多項式はすべて原始的である。

11.4 代数閉包 $\overline{\mathbb{F}}_p$

$\overline{\mathbb{F}}_p$ を $\mathbb{F}_p$ の代数閉包とする（第8章定理 8.31）。各 $n$ について $\mathbb{F}_{p^n} := \lbrace a \in \overline{\mathbb{F}}_p \mid a^{p^n} = a \rbrace$ は $p^n$ 個の元からなる部分体で、 $p^n$ 元の部分体はこれに限る（第8章定理 8.41 の証明）。 $a \in \overline{\mathbb{F}}_p$ は $\mathbb{F}_p$ 上代数的なので $\mathbb{F}_p(a)$ は有限体で、ある $\mathbb{F}_{p^n}$ に含まれる。よって

\overline{\mathbb{F}}_p = \bigcup_{n \geq 1}\mathbb{F}_{p^n}, \qquad \mathbb{F}_{p^m} \subset \mathbb{F}_{p^n} \iff m \mid n

であり、標数 $p$ の有限体はすべてこの 1 つの体の中で考えられる。 $\overline{\mathbb{F}}_p/\mathbb{F}_p$ は無限次ガロア拡大で、そのガロア群は射有限群 $\widehat{\mathbb{Z}}$ と同型になる（第13章定理 13.17）。

11.5 トレースとノルム

以下 $K = \mathbb{F}_q$ , $L = \mathbb{F}_{q^n}$ , $\sigma = \operatorname{Fr}_q$ とする。

定義 11.9（トレース・ノルム） $a \in L$ に対し、 $\operatorname{Tr}_{L/K}(a) = \sum_{i=0}^{n-1} a^{q^i}$ をトレース (trace)、 $N_{L/K}(a) = \prod_{i=0}^{n-1} a^{q^i} = a^{(q^n-1)/(q-1)}$ をノルム (norm) という。

$\sigma$ はこれらを保つので値は $L^{\langle\sigma\rangle} = K$ に属し、 $\operatorname{Tr}$ は $K$ 線形写像（ $c \in K$ は $c^q = c$ ）、 $N$ は乗法的である。 $a$ が $L$ を生成し、最小多項式が $x^n + c_{n-1}x^{n-1} + \cdots + c_0$ なら、根は $a^{q^i}$ なので $\operatorname{Tr}(a) = -c_{n-1}$ , $N(a) = (-1)^nc_0$ 。

定理 11.10

$\operatorname{Tr}_{L/K}\colon L \to K$ は全射で、その核の元の個数は $q^{n-1}$ 。

$N_{L/K}\colon L^\times \to K^\times$ は全射準同型で、その核の元の個数は $(q^n - 1)/(q - 1)$ 。

（推移律） $K \subset M \subset L$ について $\operatorname{Tr}_{L/K} = \operatorname{Tr}_{M/K} \circ \operatorname{Tr}_{L/M}$ , $N_{L/K} = N_{M/K} \circ N_{L/M}$ 。

証明. (1) $\operatorname{Tr}(a)$ は $a$ の $q^{n-1}$ 次の多項式なので、 $\operatorname{Tr}(a) = 0$ となる $a$ は高々 $q^{n-1} < q^n$ 個で（第5章系 5.30）、 $\operatorname{Tr} \neq 0$ 。 $1$ 次元の $K$ への $0$ でない $K$ 線形写像なので全射で、核は $n - 1$ 次元。(2) $L^\times$ の生成元 $\gamma$ について $N(\gamma) = \gamma^{(q^n-1)/(q-1)}$ の位数は $q - 1$ なので、像は $K^\times$ 全体。(3) $M = \mathbb{F}_{q^m}$ , $n = mk$ とすると、 $\operatorname{Fr}_q$ は加法を保つので

\operatorname{Tr}_{M/K}(\operatorname{Tr}_{L/M}(a)) = \sum_{i=0}^{m-1}\Bigl(\sum_{j=0}^{k-1} a^{q^{mj}}\Bigr)^{q^i} = \sum_{i=0}^{m-1}\sum_{j=0}^{k-1} a^{q^{mj+i}}

で、 $mj + i$ は $0, \dots, n - 1$ をちょうど 1 回ずつ動く。ノルムも同様。 $\square$

例 11.11 例 11.1(2) の $\mathbb{F}_{16}/\mathbb{F}_2$ では、最小多項式 $x^4 + x + 1$ より $\operatorname{Tr}(\alpha) = 0$ , $N(\alpha) = 1$ 。表から計算すると、トレースが $0$ の元は $0, 1, \alpha, \alpha^2, \alpha^4, \alpha^5, \alpha^8, \alpha^{10}$ の $8 = 2^3$ 個である。 $\mathbb{F}_9/\mathbb{F}_3$ では $(a + bi)^3 = a - bi$ なので $N(a + bi) = a^2 + b^2$ , $\operatorname{Tr}(a + bi) = 2a$ で、 $N(1) = 1$ , $N(1 + i) = 2$ からノルムの全射性がわかる。

11.6 ヒルベルトの定理 90

定理 11.12（ヒルベルトの定理 90, Hilbert's Theorem 90。有限体の場合）

（乗法版） $a \in L^\times$ について、 $N_{L/K}(a) = 1$ $\iff$ $a = b/\sigma(b) = b^{1-q}$ となる $b \in L^\times$ がある。

（加法版） $a \in L$ について、 $\operatorname{Tr}_{L/K}(a) = 0$ $\iff$ $a = b - \sigma(b) = b - b^q$ となる $b \in L$ がある。

証明. (1) $N \circ \sigma = N$ より $N(b/\sigma(b)) = 1$ 。逆に、準同型 $b \mapsto b^{1-q}$ の核は $b^{q-1} = 1$ となる元全体 $K^\times$ なので、像は $(q^n - 1)/(q - 1)$ 個の元からなる。像は $\operatorname{Ker} N$ に含まれ、定理 11.10(2) より元の個数が等しいので一致する。(2) 同様に、 $K$ 線形写像 $b \mapsto b - b^q$ の核は $K$ なので像は $q^{n-1}$ 個の元からなり、 $\operatorname{Tr} \circ \sigma = \operatorname{Tr}$ より $\operatorname{Ker}\operatorname{Tr}$ に含まれ、定理 11.10(1) より一致する。 $\square$

一般の巡回拡大でも同じ主張が成り立つ（第9章補題 9.20 のデデキントの補題を使う。証明は省略する）。加法版は標数 2 の 2 次方程式に応用できる。標数 2 では解の公式が使えないので、これは実用上も重要である。

系 11.13 $L = \mathbb{F}_{2^n}$ , $a \in L$ とする。 $x^2 + x + a = 0$ が $L$ に根をもつ $\iff$ $\operatorname{Tr}_{L/\mathbb{F}_2}(a) = 0$ 。

証明. 標数 2 では $b^2 + b = b - \operatorname{Fr}_2(b)$ なので、定理 11.12(2)（ $K = \mathbb{F}_2$ ）による。 $\square$

11.7 有限体上の多項式の因数分解

$f \in \mathbb{F}_q[x]$ の因数分解は、(i) 重複する因子を分ける無平方分解 (squarefree factorization)、(ii) 既約因子を次数ごとにまとめる次数別分解、(iii) 同じ次数の因子を分ける等次数分解 (equal-degree factorization) の順に行うのが標準的である。

命題 11.14 モニックな $f \in \mathbb{F}_q[x]$ を $f = \prod_i \pi_i^{e_i}$ （ $\pi_i$ は相異なるモニック既約多項式）と分解する。

$\gcd(f, f') = \prod_{p \nmid e_i}\pi_i^{e_i - 1}\prod_{p \mid e_i}\pi_i^{e_i}$ 。特に $f/\gcd(f, f') = \prod_{p \nmid e_i}\pi_i$ は無平方（重複する既約因子をもたない）である。

$f' = 0$ $\iff$ すべての $e_i$ が $p$ の倍数 $\iff$ $f = g^p$ となる $g \in \mathbb{F}_q[x]$ がある。

証明. (1) $f' = \sum_i e_i\pi_i'\pi_i^{e_i - 1}\prod_{j \neq i}\pi_j^{e_j}$ 。 $\mathbb{F}_q$ は完全体なので $\pi_i$ は分離的で（第8章定理 8.39）、 $\pi_i \nmid \pi_i'$ 。よって $\pi_i^{e_i - 1}$ は $f'$ を割り、 $\pi_i^{e_i}$ が $f'$ を割るのは第 $i$ 項が $0$ 、すなわち $p \mid e_i$ のときに限る。(2) 前半は (1) から（ $f' = 0$ $\iff$ $\gcd(f, f') = f$ ）。 $f = \sum_j c_jx^{pj}$ なら（第8章命題 8.36(3)）、 $\mathbb{F}_q$ でフロベニウスは全単射なので $c_j = d_j^p$ と書け、 $f = (\sum_j d_jx^j)^p$ 。逆は $(g^p)' = pg^{p-1}g' = 0$ 。 $\square$

命題 11.14 により、因数分解は無平方な多項式の場合に帰着する。 $g_k = \prod_{e_i = k}\pi_i$ （該当する $i$ がなければ $1$ ）とおくと、 $g_k$ は無平方で互いに素で、 $f = \prod_{k \geq 1}g_k^k$ となる。これを $f$ の無平方分解といい、各 $g_k$ を分解すれば $f$ が分解できる。 $f$ が 1 次以上のとき、次の手順で求めた $g_k$ は $f$ の無平方分解を与える。

$c = \gcd(f, f')$ , $w = f/c$ , $j = 1$ とし、すべての $g_k$ を $1$ としておく（ $f' = 0$ なら $c = f$ , $w = 1$ ）。
$w \neq 1$ である間、 $y = \gcd(w, c)$ , $g_j = w/y$ とし、 $w, c, j$ をそれぞれ $y, c/y, j + 1$ に置き換える。
手順 2 が終わったとき $c \neq 1$ なら、 $c = h^p$ となる $h$ を係数の $p$ 乗根から求め（命題 11.14(2) の証明）、 $h$ の無平方分解 $h = \prod_k h_k^k$ をこの手順で求めて、 $g_{pk} = h_k$ とする。

証明. 手順 2 の $j$ 回目の初めに

w = \prod_{p \nmid e_i,\ e_i \geq j}\pi_i, \qquad c = \prod_{p \nmid e_i,\ e_i \geq j}\pi_i^{e_i - j}\prod_{p \mid e_i}\pi_i^{e_i}

であることを $j$ についての帰納法で示す。 $j = 1$ では命題 11.14(1) である。 $w$ の既約因子のうち $c$ を割るのは $e_i > j$ のものだけなので、 $y = \prod_{p \nmid e_i,\ e_i > j}\pi_i$ , $g_j = w/y = \prod_{p \nmid e_i,\ e_i = j}\pi_i$ で（ $p \mid j$ なら $1$ ）、置き換えた後の $w, c$ は $j + 1$ についての上の式になる。 $j > \max_i e_i$ なら $w = 1$ なので手順 2 は有限回で終わり、 $c = \prod_{p \mid e_i}\pi_i^{e_i}$ が残る。 $\mathbb{F}_q[x]$ は整域なので環準同型 $u \mapsto u^p$ （第5章命題 5.36）は単射であり、 $h = \prod_{p \mid e_i}\pi_i^{e_i/p}$ である。 $\deg h \leq \deg f/p < \deg f$ なので、 $\deg f$ についての帰納法により手順 3 で $h_k = \prod_{e_i = pk}\pi_i = g_{pk}$ が求まる。 $\square$

このように、 $p \mid e_i$ となる $\pi_i$ は $f/\gcd(f, f')$ に現れず、 $\pi_i^{e_i}$ がそのまま $\gcd(f, f')$ に残って手順 3 で扱われる。たとえば $\mathbb{F}_3$ 上の $f = x^3(x + 1)^2(x + 2) = x^6 + x^5 + 2x^4 + 2x^3$ では、 $f' = 2x^4 + 2x^3$ より $c = x^3(x + 1)$ , $w = (x + 1)(x + 2)$ である。手順 2 で $g_1 = x + 2$ , $g_2 = x + 1$ が求まって $c = x^3$ が残り、手順 3 で $h = x$ から $g_3 = x$ を得る。以下 $f$ は無平方とする。

定理 11.15（次数別分解, distinct-degree factorization） $f \in \mathbb{F}_q[x]$ をモニックで無平方とし、その $d$ 次の既約因子すべての積を $f_d$ とする。 $g_0 = f$ とし、 $d = 1, 2, \dots$ について順に $h_d = \gcd(g_{d-1}, x^{q^d} - x)$ , $g_d = g_{d-1}/h_d$ とおくと、 $h_d = f_d$ である。

証明. $d$ についての帰納法で $g_{d-1} = \prod_{e \geq d} f_e$ としてよい。定理 11.2 より $x^{q^d} - x$ は次数が $d$ の約数である既約多項式の積なので、 $f$ が無平方であることから、 $h_d$ は $g_{d-1}$ の既約因子のうち次数が $d$ の約数のもの、すなわち次数 $d$ のものの積 $f_d$ である。 $\square$

実際には $x^{q^d} \bmod g_{d-1}$ を前の段の値の $q$ 乗として反復 2 乗法で計算し、 $\deg g_d < 2(d + 1)$ となれば残りの $g_d$ は既約（または $1$ ）として止める。

定理 11.16（カントール–ザッセンハウスの等次数分解, Cantor–Zassenhaus） $q$ を奇数、 $f \in \mathbb{F}_q[x]$ をモニックで無平方、既約因子はすべて $d$ 次で $r \geq 2$ 個とし、 $e = (q^d - 1)/2$ とする。 $\deg a < rd$ の $a \in \mathbb{F}_q[x]$ （ $q^{rd}$ 個）を一様にランダムに選ぶと、 $\gcd(a, f)$ または $\gcd(a^e - 1, f)$ が $f$ の自明でない因子（ $1$ でも $f$ でもない）になる確率は $1/2$ 以上である。

証明. $f = \pi_1 \cdots \pi_r$ とすると、中国剰余定理（第5章定理 5.23）より $\mathbb{F}_q[x]/(f) \cong \prod_{i=1}^r \mathbb{F}_q[x]/(\pi_i)$ で、各成分は $q^d$ 元体である。 $\deg a < rd$ の $a$ は $\mathbb{F}_q[x]/(f)$ の元と 1 対 1 に対応するので、 $a$ の成分 $(a_1, \dots, a_r)$ は一様に分布する。 $\gcd(a, f) = \prod_{a_i = 0}\pi_i$ なので、 $0$ の成分と $0$ でない成分がともにあれば成功する。すべて $a_i \neq 0$ のとき、 $(a_i^e)^2 = 1$ より $a_i^e = \pm 1$ で、巡回群 $\mathbb{F}_{q^d}^\times$ （位数 $2e$ ）では $a_i^e = 1$ となる元（平方元）と $-1$ となる元がちょうど $e$ 個ずつある。 $\gcd(a^e - 1, f) = \prod_{a_i^e = 1}\pi_i$ なので、失敗するのは $a = 0$ のときと、すべての $a_i^e$ が $1$ またはすべて $-1$ のときで、その確率は $Q = q^d \geq 3$ として

\frac{1 + 2e^r}{Q^r} = \frac{1 + 2^{1-r}(Q - 1)^r}{Q^r} \leq \frac{1 + (Q - 1)^r/2}{Q^r} \leq \frac{1}{2}

である（最後は $Q^r - (Q - 1)^r = \sum_{k=0}^{r-1}Q^k(Q - 1)^{r-1-k} \geq r \geq 2$ による）。 $\square$

1 回の成功確率は $1/2$ 以上なので、成功までの試行回数の期待値は 2 以下である。得られた因子に再帰的に適用すれば $f$ は既約因子に分かれる。 $q$ が偶数のときは $a^e - 1$ の代わりに $a + a^2 + a^4 + \cdots + a^{2^{kd-1}}$ （ $q = 2^k$ ）を使う（主張のみ）。

例 11.17 $f = x^4 + 1 \in \mathbb{F}_3[x]$ は $f' = x^3$ と互いに素なので無平方。 $x^4 = -1$ の解は位数 8 で $\mathbb{F}_3^\times$ に属さないので $h_1 = 1$ 。 $x^9 = x(x^4)^2 \equiv x \pmod f$ より $h_2 = \gcd(f, x^9 - x) = f$ で、既約因子は 2 次式 2 個である。等次数分解（ $d = 2$ , $e = 4$ ）では、 $a = x$ なら $a^4 \equiv -1$ で失敗する（ $x$ はどちらの成分でも平方でない）。 $a = x + 1$ なら $(x + 1)^4 \equiv x^4 + x^3 + x + 1 \equiv x^3 + x$ で、互除法により $\gcd(f, x^3 + x - 1) = x^2 + 2x + 2$ 。よって $x^4 + 1 = (x^2 + 2x + 2)(x^2 + x + 2)$ 。

ベルレカンプ法 (Berlekamp's algorithm。紹介)：無平方な $f$ について $B = \lbrace a \bmod f \mid a^q \equiv a \pmod f \rbrace$ は $\mathbb{F}_q[x]/(f)$ の部分空間で、中国剰余定理の成分で見ると「全成分が $\mathbb{F}_q$ に属する元」全体なので、 $\dim B$ は既約因子の個数に等しい。 $B$ は $a \mapsto a^q - a$ を表す行列の核として計算でき、 $a \in B \setminus \mathbb{F}_q$ をとると $a^q - a = \prod_{c \in \mathbb{F}_q}(a - c)$ より $f = \prod_{c \in \mathbb{F}_q}\gcd(f, a - c)$ が自明でない分解を与える。 $q$ が小さいときに有効な決定的アルゴリズムである。

11.8 シュヴァレー–ワーニングの定理

補題 11.18 整数 $k \geq 0$ について（ $0^0 = 1$ とする）、 $\sum_{a \in \mathbb{F}_q} a^k$ は $k \geq 1$ かつ $(q - 1) \mid k$ なら $-1$ 、それ以外なら $0$ である。

証明. $k = 0$ なら和は $q = 0$ 。 $k \geq 1$ なら $S = \sum_{a \neq 0}a^k$ を考える。 $(q - 1) \mid k$ なら各項は $1$ で $S = q - 1 = -1$ 。そうでなければ $\mathbb{F}_q^\times$ の生成元 $g$ について $g^k \neq 1$ で、 $a \mapsto ga$ は $\mathbb{F}_q^\times$ の全単射なので $S = g^kS$ 、よって $S = 0$ 。 $\square$

定理 11.19（シュヴァレー–ワーニングの定理, Chevalley–Warning theorem） $f_1, \dots, f_r \in \mathbb{F}_q[x_1, \dots, x_n]$ が $\sum_i \deg f_i < n$ をみたせば、共通零点の集合 $V \subset \mathbb{F}_q^n$ の元の個数は $p$ で割り切れる。特に $f_i$ の定数項がすべて $0$ なら、 $V$ は $0$ 以外の点を含む（シュヴァレーの定理）。

証明. $P = \prod_{i=1}^r(1 - f_i^{q-1})$ とおくと、 $c \neq 0$ なら $c^{q-1} = 1$ なので、 $P(x)$ は $x \in V$ なら $1$ 、そうでなければ $0$ 。よって $\mathbb{F}_q$ において $\lvert V \rvert \cdot 1 = \sum_{x \in \mathbb{F}_q^n}P(x)$ 。 $\deg P < (q - 1)n$ なので $P$ の各単項式 $x_1^{k_1} \cdots x_n^{k_n}$ はある $k_j < q - 1$ をもち、補題 11.18 より

\sum_{x \in \mathbb{F}_q^n} x_1^{k_1} \cdots x_n^{k_n} = \prod_{j=1}^{n}\sum_{x_j \in \mathbb{F}_q} x_j^{k_j} = 0

よって $\lvert V \rvert \equiv 0 \pmod p$ 。後半は $0 \in V$ より $\lvert V \rvert \geq p \geq 2$ から従う。 $\square$

たとえば、 $\mathbb{F}_q$ 上の 3 変数以上の 2 次形式は自明でない零点をもつ。 $x^2 + y^2 - z^2 = 0$ の $\mathbb{F}_p^3$ における解は $p^2$ 個で（問題 11.8）、確かに $p$ で割り切れる。

11.9 有限体上の二次曲線の点の個数

$q$ を奇数とし、平方指標 (quadratic character) $\eta\colon \mathbb{F}_q \to \lbrace 0, \pm 1 \rbrace$ を $\eta(0) = 0$ 、 $a$ が $\mathbb{F}_q^\times$ の元の平方なら $\eta(a) = 1$ 、そうでなければ $-1$ と定める（ $q = p$ ならルジャンドル記号 $\left(\frac{a}{p}\right)$ 。第1章定義 1.46）。 $\mathbb{F}_q^\times$ は偶数位数の巡回群なので、平方元は指数 2 の部分群をなし、 $\eta$ は乗法的で $\sum_{a \in \mathbb{F}_q}\eta(a) = 0$ 、 $x^2 = a$ の解の個数は $1 + \eta(a)$ である。

定理 11.20 $q$ を奇数、 $a, b, c \in \mathbb{F}_q^\times$ とすると、 $ax^2 + by^2 = c$ の解 $(x, y) \in \mathbb{F}_q^2$ の個数は $q - \eta(-ab)$ である。特に奇素数 $p$ について、 $x^2 + y^2 = 1$ の $\mathbb{F}_p$ における解の個数は $p - \left(\frac{-1}{p}\right)$ 、すなわち $p \equiv 1 \pmod 4$ なら $p - 1$ 、 $p \equiv 3 \pmod 4$ なら $p + 1$ である。

証明. $ax^2 = u$ をみたす $x$ は $1 + \eta(u/a) = 1 + \eta(au)$ 個なので、解の個数は

N = \sum_{u + v = c}\bigl(1 + \eta(au)\bigr)\bigl(1 + \eta(bv)\bigr) = q + \sum_u \eta(au) + \sum_v \eta(bv) + \eta(ab)\sum_{u \in \mathbb{F}_q}\eta\bigl(u(c - u)\bigr)

で、第 2・3 項は $0$ 。 $u \neq 0$ なら $\eta(u(c - u)) = \eta(u^2(c/u - 1)) = \eta(c/u - 1)$ で、 $u$ が $\mathbb{F}_q^\times$ を動くと $w = c/u - 1$ は $\mathbb{F}_q \setminus \lbrace -1 \rbrace$ を動く。よって最後の和は $\sum_{w \neq -1}\eta(w) = -\eta(-1)$ で、 $N = q - \eta(-ab)$ 。後半は第1章系 1.50(2) による。 $\square$

例 11.21 $p = 7$ では $x^2 + y^2 = 1$ の解は $8$ 個： $(0, \pm 1)$ , $(\pm 1, 0)$ , $(\pm 2, \pm 2)$ （ $4 + 4 = 8 \equiv 1$ ）。射影平面の曲線 $x^2 + y^2 = z^2$ で考えると、無限遠点（ $z = 0$ ）を合わせて点の個数はつねに $p + 1$ になる（問題 11.8）。

楕円曲線 $y^2 = f(x)$ の（無限遠点以外の）点も同じように $\sum_x\bigl(1 + \left(\frac{f(x)}{p}\right)\bigr)$ 個と数えられるが、この和は簡単には求まらず、ハッセの定理による評価が要になる（21-elliptic-curves 第4章）。

11.10 応用：CRC・AES・リード–ソロモン符号

CRC. ビット列 $b_{m-1} \cdots b_1b_0$ を多項式 $\sum b_ix^i \in \mathbb{F}_2[x]$ と同一視する。 $r$ 次の生成多項式 (generator polynomial) $G$ を決めておき、送信者はメッセージ $M$ について $R = x^rM \bmod G$ を計算し、 $T = x^rM + R$ （ $M$ の後ろに $R$ の $r$ ビットを付けたもの）を送る。 $G \mid T$ なので、受信者は受け取った列が $G$ で割り切れるかを調べる。誤りのパターンを $E$ （反転したビットの位置の多項式）とすると、誤りを見逃すのは $G \mid E$ のときに限る。これが CRC（巡回冗長検査, cyclic redundancy check）である。

命題 11.22 $G$ を $G(0) = 1$ の $r$ 次式（ $r \geq 1$ ）とする。

長さ $r$ 以下のバースト誤り $E = x^iB$ （ $B(0) = 1$ , $\deg B < r$ 。1 ビットの誤りは $B = 1$ ）は検出される。

$(x + 1) \mid G$ なら、奇数個のビットの誤りは検出される。

$\overline{x}$ の $(\mathbb{F}_2[x]/(G))^\times$ における位数を $e$ とすると、 $0 < j - i < e$ の 2 ビットの誤り $x^i + x^j$ は検出される。 $G$ が原始多項式なら $e = 2^r - 1$ 。

証明. (1) $\gcd(G, x) = 1$ なので、 $G \mid x^iB$ なら $G \mid B$ となり、 $B \neq 0$ , $\deg B < r$ に反する。(2) $E(1)$ は反転したビット数の偶奇を表すので奇数個なら $E(1) = 1$ だが、 $G \mid E$ なら $(x + 1) \mid E$ で $E(1) = 0$ 。(3) $G \mid x^i(1 + x^{j-i})$ なら $G \mid x^{j-i} - 1$ で、 $e \mid j - i$ 。 $\square$

例 11.23 $G = x^4 + x + 1$ （原始多項式、 $e = 15$ ）、 $M = 1101011011$ とすると、 $x^4M$ を $G$ で割った余りは $R = 1110$ で、送信列は $11010110111110$ 。この $G$ は長さ 4 以下のバースト誤りと、間隔が 15 未満の 2 ビットの誤りを検出する。イーサネット（IEEE 802.3）などで使われる CRC-32 の 32 次の生成多項式も $\mathbb{F}_2$ 上の原始多項式である（計算機で確かめられる）。

AES. 共通鍵暗号 AES（NIST の規格 FIPS 197。規格は改訂されうる）では、バイト $b_7 \cdots b_0$ を $\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(m)$ , $m = x^8 + x^4 + x^3 + x + 1$ の元 $\sum b_ix^i$ とみて、16 進 2 桁で $\lbrace 57 \rbrace$ のように書く。 $m$ は既約だが原始的ではなく、 $\lbrace 02 \rbrace = x$ の位数は 51、 $\lbrace 03 \rbrace = x + 1$ が原始元である（計算で確かめた）。和はビットごとの排他的論理和、 $x$ 倍は 1 ビットの左シフトで、あふれたら $x^8 \equiv x^4 + x^3 + x + 1$ （ $\lbrace 1b \rbrace$ ）を加える。積はこれを繰り返して計算し、逆元は $a^{-1} = a^{254}$ （ $a^{255} = 1$ ）で求まる。

def xtime(a):              # x を掛ける
    a <<= 1
    return a ^ 0x11B if a & 0x100 else a

def gf_mul(a, b):          # F_{2^8} での積
    r = 0
    while b:
        if b & 1:
            r ^= a
        a, b = xtime(a), b >> 1
    return r

def gf_inv(a):             # a^254 = a^(-1)（a != 0）
    r, e = 1, 254
    while e:
        if e & 1:
            r = gf_mul(r, a)
        a, e = gf_mul(a, a), e >> 1
    return r

print(hex(gf_mul(0x57, 0x83)), hex(gf_mul(0x57, 0x13)), hex(gf_inv(0x53)))
# 0xc1 0xfe 0xca

結果は FIPS 197 の例 $\lbrace 57 \rbrace \bullet \lbrace 83 \rbrace = \lbrace c1 \rbrace$ , $\lbrace 57 \rbrace \bullet \lbrace 13 \rbrace = \lbrace fe \rbrace$ と一致する。後者は手でも計算でき、 $\lbrace 57 \rbrace$ に $x$ を順に掛けると $\lbrace ae \rbrace, \lbrace 47 \rbrace, \lbrace 8e \rbrace, \lbrace 07 \rbrace$ となるので、 $\lbrace 13 \rbrace = x^4 + x + 1$ より $\lbrace 57 \rbrace \oplus \lbrace ae \rbrace \oplus \lbrace 07 \rbrace = \lbrace fe \rbrace$ 。AES の S ボックスは $a \mapsto a^{-1}$ （ $0 \mapsto 0$ ）に $\mathbb{F}_2$ 上のアフィン変換を合成したもので、 $\lbrace 53 \rbrace^{-1} = \lbrace ca \rbrace$ から FIPS 197 の例 $S(\lbrace 53 \rbrace) = \lbrace ed \rbrace$ が得られる（アフィン変換の式は省略する）。

リード–ソロモン符号. 相異なる $\alpha_1, \dots, \alpha_n \in \mathbb{F}_q$ をとり、 $k - 1$ 次以下の多項式 $m$ （係数 $k$ 個がメッセージ）を $(m(\alpha_1), \dots, m(\alpha_n))$ に符号化する。相異なる符号語の差は $0$ でない $k - 1$ 次以下の多項式の値なので、 $0$ になる成分は $k - 1$ 個以下（第5章系 5.30）で、符号語どうしは $n - k + 1$ 箇所以上で異なる。したがって $\lfloor (n - k)/2 \rfloor$ 個までの誤りを訂正できる。QR コードや CD で使われている。

この先. リード–ソロモン符号・BCH 符号と CRC の巡回符号としての扱いは25-cryptography-coding 第6章、有限体上の楕円曲線の点の個数とハッセの定理は21-elliptic-curves 第4章、 $\operatorname{Gal}(\overline{\mathbb{F}}_p/\mathbb{F}_p) \cong \widehat{\mathbb{Z}}$ は第13章（定理 13.17）で扱う。

まとめ

$x^{q^n} - x$ は次数が $n$ の約数のモニック既約多項式すべての積で、メビウスの反転公式から $N_q(n) = \frac{1}{n}\sum_{d \mid n}\mu(d)q^{n/d}$ （ $\mathbb{F}_2$ 上 $n = 1, \dots, 8$ で $2, 1, 2, 3, 6, 9, 18, 30$ ）。
原始元は $\varphi(q^n - 1)$ 個、 $n$ 次の原始多項式は $\varphi(q^n - 1)/n$ 個。 $\overline{\mathbb{F}}_p = \bigcup_n \mathbb{F}_{p^n}$ 。
トレースとノルムは全射で推移律をみたす。ヒルベルトの定理 90： $N(a) = 1 \iff a = b^{1-q}$ 、 $\operatorname{Tr}(a) = 0 \iff a = b - b^q$ 。
因数分解は無平方分解（ $\gcd(f, f')$ との $\gcd$ をくり返し、重複度が $p$ の倍数の因子は $p$ 乗根をとって扱う）・次数別分解（ $\gcd(f, x^{q^d} - x)$ ）・等次数分解（カントール–ザッセンハウス法。 $q$ が奇数なら 1 回の成功確率は $1/2$ 以上）の順に行う。
シュヴァレー–ワーニング：次数の和が変数の個数より小さければ、共通零点の個数は $p$ の倍数。
$ax^2 + by^2 = c$ の解は $q - \eta(-ab)$ 個。 $x^2 + y^2 = 1$ の $\mathbb{F}_p$ 上の解は $p - \left(\frac{-1}{p}\right)$ 個。
CRC・AES・リード–ソロモン符号は $\mathbb{F}_2[x]$ や $\mathbb{F}_{2^8}$ の算術の上に作られている。

演習問題

問題 11.1 ★ 例 11.1(2) の $\mathbb{F}_{16}$ で、 $(\alpha^3 + \alpha^2)(\alpha^2 + 1)$ と $(\alpha^2 + \alpha + 1)^{-1}$ を求めよ。また $x^2 + x + 1$ の $\mathbb{F}_{16}$ における根を求めよ。

解答

表より $\alpha^3 + \alpha^2 = \alpha^6$ , $\alpha^2 + 1 = \alpha^8$ なので積は $\alpha^{14} = \alpha^3 + 1$ 。 $\alpha^2 + \alpha + 1 = \alpha^{10}$ なので逆元は $\alpha^5 = \alpha^2 + \alpha$ 。 $x^2 + x + 1$ の根は位数 3 の元 $\alpha^5 = \alpha^2 + \alpha$ と $\alpha^{10} = \alpha^2 + \alpha + 1$ である。

問題 11.2 ★ $\mathbb{F}_3$ 上の 2 次のモニック既約多項式をすべて求め、系 11.4 と照合せよ。また $N_3(3)$ , $N_3(4)$ を求めよ。

解答

2 次式は $\mathbb{F}_3$ に根をもたなければ既約で、 $x^2 + 1$ , $x^2 + x + 2$ , $x^2 + 2x + 2$ の 3 個（ $0, 1, 2$ を代入して確かめる）。系 11.4 より $N_3(2) = (9 - 3)/2 = 3$ で一致する。 $N_3(3) = (27 - 3)/3 = 8$ , $N_3(4) = (81 - 9)/4 = 18$ 。

問題 11.3 ★★ $\mathbb{F}_2$ 上の 6 次既約多項式 9 個のうち原始的なものは何個か。原始的でないものについて根の位数を求め、個数が合うことを確かめよ。

解答

定理 11.6 より $\varphi(63)/6 = 36/6 = 6$ 個。6 次既約多項式の根は $\mathbb{F}_{64}$ の元で、 $\mathbb{F}_8$ （ $a^7 = 1$ ）にも $\mathbb{F}_4$ （ $a^3 = 1$ ）にも属さない。よって位数は $63$ の約数のうち $7$ も $3$ も割らない $9, 21, 63$ のどれかで、逆にこれらの位数の元は 6 次である。位数 $9$ の元は $\varphi(9) = 6$ 個で 1 個の多項式（ $x^9 - 1 = (x^3 - 1)(x^6 + x^3 + 1)$ より $x^6 + x^3 + 1$ ）、位数 $21$ の元は $\varphi(21) = 12$ 個で 2 個の多項式、位数 $63$ は原始多項式 6 個で、計 $1 + 2 + 6 = 9 = N_2(6)$ 。

問題 11.4 ★★ 系 11.13 を使って、例 11.1(2) の $\mathbb{F}_{16}$ で $x^2 + x + \alpha = 0$ は解をもち、 $x^2 + x + \alpha^3 = 0$ は解をもたないことを示し、前者の解を求めよ。

解答

$\operatorname{Tr}(\alpha) = 0$ （例 11.11）。 $\operatorname{Tr}(\alpha^3) = \alpha^3 + \alpha^6 + \alpha^{12} + \alpha^{24}$ で、 $\alpha^{24} = \alpha^9$ なので、表より $1000 + 1100 + 1111 + 1010 = 0001$ 、すなわち $\operatorname{Tr}(\alpha^3) = 1$ 。よって前者だけが解をもつ。 $b = \alpha^9 = \alpha^3 + \alpha$ とすると $b^2 + b = \alpha^{18} + \alpha^9 = \alpha^3 + \alpha^3 + \alpha = \alpha$ で、解は $\alpha^3 + \alpha$ と $\alpha^3 + \alpha + 1$ 。

問題 11.5 ★★ $n \geq 2$ について $(q^n - 2q^{n/2})/n < N_q(n) \leq q^n/n$ を示せ。

解答

上の不等式は (1) から。(1) より各 $d$ で $dN_q(d) \leq q^d$ なので、 $m = \lfloor n/2 \rfloor$ とすると

nN_q(n) = q^n - \sum_{d \mid n,\ d < n} dN_q(d) \geq q^n - \sum_{d=1}^{m} q^d = q^n - \frac{q^{m+1} - q}{q - 1} > q^n - \frac{q}{q - 1}q^m \geq q^n - 2q^{n/2}

（ $n$ の真の約数は $n/2$ 以下で、 $q/(q - 1) \leq 2$ ）。

問題 11.6 ★★ 次数別分解で $x^5 + x^4 + 1 \in \mathbb{F}_2[x]$ を因数分解せよ。

解答

$f' = 5x^4 + 4x^3 = x^4$ で $f(0) = 1$ より $\gcd(f, f') = 1$ 、 $f$ は無平方。 $f(0) = f(1) = 1$ より $h_1 = \gcd(f, x^2 + x) = 1$ 。 $x^4 + x = x(x + 1)(x^2 + x + 1)$ で、 $x^3 \equiv 1 \pmod{x^2 + x + 1}$ より $f \equiv x^2 + x + 1 \equiv 0$ なので、 $h_2 = \gcd(f, x^4 + x) = x^2 + x + 1$ 。 $g_2 = f/h_2 = x^3 + x + 1$ は $\deg g_2 = 3 < 6$ なので既約。よって $x^5 + x^4 + 1 = (x^2 + x + 1)(x^3 + x + 1)$ 。

問題 11.7 ★★★ $p$ を素数とする。任意の $2p - 1$ 個の整数 $a_1, \dots, a_{2p-1}$ の中から、和が $p$ で割り切れる $p$ 個を選べることを示せ（エルデシュ–ギンツブルク–ジフの定理の素数の場合。ヒント：定理 11.19 を 2 つの多項式 $\sum_i a_ix_i^{p-1}$ , $\sum_i x_i^{p-1}$ に使う）。

解答

$\mathbb{F}_p$ 上の $2p - 1$ 変数の多項式 $f_1 = \sum_i a_ix_i^{p-1}$ , $f_2 = \sum_i x_i^{p-1}$ は次数の和 $2p - 2 < 2p - 1$ で、定数項は $0$ 。定理 11.19 より $0$ でない共通零点 $x$ がある。 $S = \lbrace i \mid x_i \neq 0 \rbrace$ とおくと、 $i \in S$ なら $x_i^{p-1} = 1$ なので、 $f_2(x) = 0$ より $\lvert S \rvert \equiv 0 \pmod p$ 。 $1 \leq \lvert S \rvert \leq 2p - 1$ より $\lvert S \rvert = p$ で、 $f_1(x) = 0$ より $\sum_{i \in S}a_i \equiv 0 \pmod p$ 。

問題 11.8 ★★ $p$ を奇素数とする。(1) 射影平面の曲線 $x^2 + y^2 = z^2$ の $\mathbb{F}_p$ 有理点（ $\mathbb{P}^2(\mathbb{F}_p)$ の点）は $p + 1$ 個であることを示せ。(2) $x^2 + y^2 - z^2 = 0$ の $\mathbb{F}_p^3$ における解は $p^2$ 個であることを示せ。

解答

(1) $z \neq 0$ の点は $z = 1$ と正規化でき、定理 11.20 より $p - \left(\frac{-1}{p}\right)$ 個。 $z = 0$ の点は $x^2 + y^2 = 0$ , $(x, y) \neq (0, 0)$ で、 $y = 0$ なら $x = 0$ となるので $y = 1$ と正規化でき、 $x^2 = -1$ の解 $1 + \left(\frac{-1}{p}\right)$ 個。合計 $p + 1$ 。(2) $0$ 以外の解は射影平面の点 1 つにつき $p - 1$ 個（ $\mathbb{F}_p^\times$ 倍）あるので、 $(p + 1)(p - 1) + 1 = p^2$ 個（ $+1$ は $0$ ）。

問題 11.9 ★★ $p \equiv 3 \pmod 4$ を素数とする。(1) $\mathbb{F}_{p^2} = \mathbb{F}_p(i)$ （ $i^2 = -1$ ）と書けることを示せ。(2) $N_{\mathbb{F}_{p^2}/\mathbb{F}_p}(x + yi) = x^2 + y^2$ を示し、定理 11.10(2) を使って $x^2 + y^2 = 1$ の $\mathbb{F}_p$ における解が $p + 1$ 個であることを示せ（定理 11.20 の別証明）。(3) $p = 3$ のとき、ノルムが $1$ の元をヒルベルトの定理 90 の形 $b^{1-3}$ で書け。

解答

(1) 第1章系 1.50(2) より $-1$ は法 $p$ の平方非剰余なので、 $x^2 + 1$ は $\mathbb{F}_p$ 上既約で、 $\mathbb{F}_p[x]/(x^2 + 1) = \mathbb{F}_p(i)$ は $p^2$ 元体である。(2) $p - 3$ は 4 の倍数なので $i^p = (i^4)^{(p-3)/4}i^3 = -i$ 、よって $(x + yi)^p = x - yi$ で、 $N(x + yi) = (x + yi)(x - yi) = x^2 + y^2$ 。定理 11.10(2) より $N(z) = 1$ となる $z$ は $(p^2 - 1)/(p - 1) = p + 1$ 個で、これは $x^2 + y^2 = 1$ の解 $(x, y)$ と 1 対 1 に対応する。(3) ノルム $1$ の元は $1, 2, i, 2i$ の 4 個。 $g = 1 + i$ のべき（例 11.1(1)）を使うと $b^{1-3} = b^{-2}$ は $b = 1, g, g^2, g^3$ に対し $1, g^6 = i, g^4 = 2, g^2 = 2i$ となる。