位数が素数でない有限体に関する基本的なことが分かっていなかったので調べた

有限体のことを分かったつもりでいました

有限体には位数が素数のものとそうでないもの、つまり位数が素数冪となるものがある。前者は素数 $p$ を用いて $\mathbb{Z}/p\mathbb{Z}$ を考えればよいので簡単だが、後者はちょっとだけややこしい。とは言っても、位数が $q=p^n$ なら適当に $\mathbb{F}_p$ 上の $n$ 次既約多項式 $f(x)$ を持ってきて $\mathbb{F}_q = \mathbb{F}_p[x]/(f(x))$ とすればいいんでしょ？と、その程度の認識だった。それで、 $f(\alpha)=0$ となるような $\alpha$ によって具体的な元が $\sum_{i=0}^{n-1} c_i \alpha^{i} (c_i \in \mathbb{F}_p )$ みたいに書けるんでしょ？と、それで分かったつもりになっていた。

ところが、最近になっていろいろと分かっていないことがあることに気づいた。それは具体的には以下の3点である。

既約多項式の選択の仕方によらず $\alpha$ は $\mathbb{F}_q^{\times}$ の生成元になると思っていたが、その理解は正しいのか？
既約多項式の根として適当に $\alpha$ を選んでいるが、既約多項式の根は一つとは限らない。これまで根の選択方法について考えたことがなかったが、適当に選んでしまって大丈夫なのか？
$\mathbb{F}_q$ の元の $\mathbb{F}_p$ 上の最小多項式の次数はどうなるのか？特に、次数が $n$ より大きくなることはあり得るのか？

本稿ではこれらの疑問の答えを順に解き明かしていく。以下では $q=p^n$ であるとする。

疑問1：既約多項式の根は常に $\mathbb{F}_q^{\times}$ の生成元になるのか？

必ずしもそうなるとは限らない。そのような性質を満たす多項式を原始多項式と呼ぶ。逆に言えば、 $f(x)$ が原始多項式なら $f(x)$ の根 $\alpha$ が $\mathbb{F}_q^{\times}$ の生成元になる。これは実際に例を見れば一目瞭然なので、以下で見てみよう。なお、例に使った多項式は[1]を参考にした。

原始多項式の例

Sageで $\mathbb{F}_{16}$ を特別な引数なしで生成すると、既約多項式として $x^4 + x + 1$ が選ばれる。これは原始多項式である。実際、多項式の根aの冪を順番に計算すると15乗して初めて1になることが分かる。

sage: F.<a> = GF(16)
sage: F.modulus()
x^4 + x + 1
sage: F.modulus().is_primitive()
True
sage: for i in range(1, len(F)):
....:     print(f"{i:<2}: {a**i}")
....:
1 : a
2 : a^2
3 : a^3
4 : a + 1
5 : a^2 + a
6 : a^3 + a^2
7 : a^3 + a + 1
8 : a^2 + 1
9 : a^3 + a
10: a^2 + a + 1
11: a^3 + a^2 + a
12: a^3 + a^2 + a + 1
13: a^3 + a^2 + 1
14: a^3 + 1
15: 1
sage:

原始多項式ではない既約多項式の例

今度は $\mathbb{F}_{16}$ を $x^4 + x^3 + x^2 + x + 1$ を指定して生成してみる。これは原始多項式ではない。実際、多項式の根aの冪を順番に計算すると5乗した時点で1になることが分かる。

sage: P.<x> = GF(2)[]
sage: F.<a> = GF(16, modulus=x^4 + x^3 + x^2 + x + 1)
sage: F.modulus()
x^4 + x^3 + x^2 + x + 1
sage: F.modulus().is_primitive()
False
sage: for i in range(1, len(F)):
....:     print(f"{i:<2}: {a**i}")
....:
1 : a
2 : a^2
3 : a^3
4 : a^3 + a^2 + a + 1
5 : 1
6 : a
7 : a^2
8 : a^3
9 : a^3 + a^2 + a + 1
10: 1
11: a
12: a^2
13: a^3
14: a^3 + a^2 + a + 1
15: 1
sage:

疑問2：既約多項式の根の選び方はどうすればよいのか？

これは適当でよい。 $n$ 次既約多項式 $f(x)$ の根は全て $\mathbb{F}_q$ に含まれており、かつどれを選んでも本質的には同じ有限体が得られる。

なぜそうなるのかをもう少し説明してみる。簡単に言えば以下の定理が成り立つからということになる[2]。

最小多項式の根の間の関係

$L/K$ が体の代数拡大とし, $\alpha \in L$ の $K$ 上の最小多項式を $f(x) = x^n + a_1 x^{n-1} + \cdots + a_n$ とする. このとき, $\beta \in L$ が $f(x)$ の根なら, 次の(1)－(3)が成り立つ.
(1) 割愛
(2) $f(x)$ は $\beta$ の最小多項式でもあり, $K$ 上の同型 $K(\alpha) \cong K(\beta)$ で $\alpha$ が $\beta$ に対応するものが存在する.
(3) 割愛

これより、拡大 $L/K$ は正規拡大だと言える。今はあまり関係ないが、有限体の拡大は必ず分離拡大になるので、結局ガロア拡大になる。

例

理論的には分かった気持ちになったが、例も見ておこう。以下では $f(x) = x^2 + 1$ によって生成される有限体 $\mathbb{F}_9 = \mathbb{F}_3[x]/(f(x))$ を考える。 $f(x)$ が $\mathbb{F}_3$ 上既約であることは0, 1, 2を代入して0にならないことから分かる。

根の一つを $\alpha$ と名付けると、この多項式は $(x - \alpha)(x - \alpha^3)$ と因数分解できる。と、いきなり言われてもホンマかいなという気持ちになるかもしれないので、以下で確かめておく。

$\displaystyle{ \begin{eqnarray} (x - \alpha)(x - \alpha^3) &=& x^2 - (\alpha^3 + \alpha) + \alpha^4 \\ &=& x^2 - \alpha(\alpha^2 + 1) + (\alpha^2 + 1)(\alpha^2 - 1) + 1 \\ &=& x^2 + 1 \end{eqnarray} }$

このようにして構成した $\mathbb{F}_9$ の元を具体的に書き出してみると以下のようになる。

$0$
$1$
$2$
$\alpha$
$\alpha+1$
$\alpha+2$
$2\alpha$
$2\alpha+1$
$2\alpha+2$

ここで $\beta = \alpha^3 = 2\alpha$ と置く。すると、 $\mathbb{F}_9$ の元は以下のように書ける（分かりやすさのために並びは上述のものと対応するようにした）。

$0$
$1$
$2$
$2\beta$
$2\beta+1$
$2\beta+2$
$\beta$
$\beta+1$
$\beta+2$

このように $\beta$ を使った表現は単に $\alpha$ を使った表現の記号を $\beta$ に置き換えただけという形になっており、明らかに体として同じ構造を持っていることが分かる。

また、実は $\alpha= \beta^3$ であるため、 $f(x) = (x-\beta)(x-\beta^3)$ と書いても同じである。これも形式的には記号を置き換えただけになっていて、 $\alpha$ と $\beta$ の綺麗な対称性が見て取れる。

疑問3：有限体の元の最小多項式の次数はどうなるのか？

これは $n$ 次以下になる。もっと言うと、任意の $\alpha \in \mathbb{F}_q$ について $\mathbb{F}_p$ 上の最小多項式の次数は $n$ を割り切るような整数となる。

この事実に関してはスパッと証明を書いてくれている文献を見つけられなかったので、AIの助けを借りつつ自分で考えてみた。

まず、 $\alpha$ を $\mathbb{F}_p$ に添加した体 $\mathbb{F}_p(\alpha)$ を考える。このとき、体の拡大 $\mathbb{F}_p(\alpha)/\mathbb{F}_p$ および $\mathbb{F}_q/\mathbb{F}_p$ の拡大次数の間には以下のような関係がある。

$\displaystyle{ [\mathbb{F}_p(\alpha) : \mathbb{F}_p] \mid [\mathbb{F}_q : \mathbb{F}_p] }$

ここで、 $[\mathbb{F}_q : \mathbb{F}_p] = n$ なのは良いだろう。問題は $[\mathbb{F}_p(\alpha) : \mathbb{F}_p]$ の方だが、これは $\alpha$ の $\mathbb{F}_p$ 上の最小多項式 $m_{\alpha}(x)$ の次数に等しくなる。この点さえ納得できれば冒頭で述べた結果を得られるので、この点について詳しく見ていく。

$\phi: \mathbb{F}_p[x] \to \mathbb{F}_p(\alpha), f(x) \mapsto f(\alpha)$ という準同型を考える。 $\mathrm{Ker}\phi = \{f(x) \mid f(\alpha) = 0\} = (m_{\alpha}(x))$ となるので、準同型定理より以下が成り立つ。

$\displaystyle{ \mathbb{F}_p[x]/(m_{\alpha}(x)) \cong \mathrm{Im}\phi = \mathbb{F}_p[\alpha] }$

体の有限次拡大は代数拡大になるので、拡大 $\mathbb{F}_p(\alpha)/\mathbb{F}_p$ は代数拡大である（この事実の証明は本[2]などを参照）。これより $\alpha$ は $\mathbb{F}_p$ 上代数的なので $\mathbb{F}_p[\alpha] = \mathbb{F}_p(\alpha)$ となる（この事実の証明も本[2]などを参照）。よって以下の式が成り立つ。

$\displaystyle{ \mathbb{F}_p[x]/(m_{\alpha}(x)) \cong \mathbb{F}_p(\alpha) }$

$m_{\alpha}(x)$ の次数を $k$ とすると、 $\mathbb{F}_p[x]/(m_{\alpha}(x))$ は $1, x, \cdots, x^{k-1}$ を基底とする $\mathbb{F}_p$ 上の $k$ 次ベクトル空間になるので、結局 $[\mathbb{F}_p(\alpha) : \mathbb{F}_p] = k$ となる。よって $k \mid n$ となる。証明終わり。

例

例として $\mathbb{F}_{16}$ の各元の最小多項式を以下に示す。次数が1, 2, 4のいずれかになっており、ここまで説明してきた内容と合致することが分かる。

sage: F.<a>=GF(16)
sage: for i in range(1, len(F)):
....:     print(f"{str(a**i):<20}: {(a**i).minpoly()}")
....:
a                   : x^4 + x + 1
a^2                 : x^4 + x + 1
a^3                 : x^4 + x^3 + x^2 + x + 1
a + 1               : x^4 + x + 1
a^2 + a             : x^2 + x + 1
a^3 + a^2           : x^4 + x^3 + x^2 + x + 1
a^3 + a + 1         : x^4 + x^3 + 1
a^2 + 1             : x^4 + x + 1
a^3 + a             : x^4 + x^3 + x^2 + x + 1
a^2 + a + 1         : x^2 + x + 1
a^3 + a^2 + a       : x^4 + x^3 + 1
a^3 + a^2 + a + 1   : x^4 + x^3 + x^2 + x + 1
a^3 + a^2 + 1       : x^4 + x^3 + 1
a^3 + 1             : x^4 + x^3 + 1
1                   : x + 1
sage:

まとめ

本稿では私が有限体について理解が甘かった部分について調べ直した結果を紹介した。基本的なことほど分かったつもりになっていると怖いということを久々に思い出した。

参考

[1] qiita.com
[2] www.nippyo.co.jp ※今から購入される場合は第2版を買われるのが良いだろう。