1

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

268
0
$$\newcommand{bF}[0]{\overline{\mathbb{F}}} \newcommand{F}[0]{\mathbb{F}} $$

はじめに

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

$\F_p$の代数閉包

有限体$\F_{p^n}$$\bF_p$という大きな(有限体ではない)体から構成することができる.この体$\bF_p$$\F_p$の代数閉包と呼ばれるものであり,大雑把に言えば$\bmod p$の世界における複素数体$\mathbb{C}$のようなものである.具体的には,$\bF_p$は次のような性質を持っている:

  • $\F_p\subset \bF_p$.
  • 任意の$\bF_p$の元はある$\F_p$係数多項式の根である.
  • 任意の$\bF_p$係数多項式は$1$次式の積に因数分解できる.

$\bF_p$の具体的な構成法は少々難しく,またそれほど重要ではないので割愛する.以下の説明では上記の$3$つの性質のみを用いる

$\F_5$係数の多項式$x^2-3$$\F_5$の中に根を持たないので,$\F_5$係数の範囲ではこれ以上因数分解できないが,$\bF_5$係数の範囲では
$$ x^2-3=(x-\alpha)(x-\beta)\quad (\alpha,\beta\in \bF_p) $$
と因数分解される.係数を比較すると$\alpha+\beta=0$となるため,$\alpha$$\sqrt{3}$と書くことにすると$\beta=-\sqrt{3}$と表せる.

$\bF_p$について考える上で重要なのが$p$乗写像
$$ F\colon \bF_p\to \bF_p;\quad F(x)=x^p $$
である.これをFrobenius写像という.明らかにFrobenius写像は積および商を保つが,実は和と差も保っている:

任意の$x,y\in \bF_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^iy^{p-i}$$
が成り立つ.$i=1,2,\cdots,p-1$に対して$\dbinom{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\colon \bF_p\to \bF_p;\;F(x)=x^p$は全単射である.

$a\in \bF_p$に対して方程式$x^p=a$$\bF_p$内に解を持つので$F$は全射である.また
$$ y^p=z^p\implies (y-z)^p=0\implies y=z $$
より$F$は単射である.

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

任意の$x\in \bF_p$に対し,ある正整数$n$が存在して$x^{p^n}=x$となる.

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

$\bF_p$の元$x$に対し,$x^{p^n}=x$となる正整数$n$の最小値を$x$次数と呼ぶ.

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

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

後で使うために,$\bF_p$係数の多項式の微分を定義しておく:

$\bF_p$係数多項式$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0$に対して
$$ f'(x)=da_dx^{d-1}+(d-1)a_{d-1}x^{d-2}+\cdots+a_1 $$
と定める.

$\bF_p$係数多項式$f(x),g(x)$に対して$(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$が成り立つ.

展開することで$f(x)=ax^d,\;g(x)=bx^e$の場合に帰着できる.この場合は容易である.

有限体の構成

素冪$p^n$に対し,$\F_{p^n}=\{x\in \bF_p\mid x^{p^n}=x\}$と定める.つまり,$\F_{p^n}$は次数が$n$の約数であるような$\bF_p$の元全体からなる集合である.

Fermatの小定理より$\F_p\subset\F_{p^n}$が成り立つ.また命題2より,任意の$\bF_p$の元はある$\F_{p^n}$に含まれる.

$x,y\in \F_{p^n}$に対し,$x+y,\;x-y,\;xy\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$$\bF_p$における解全体である.$\bF_p$係数の範囲で
$$ x^{p^n}-x = \prod_{i=1}^{p^n}(x-\alpha_i) $$
と因数分解すると,$\F_{p^n}=\{\alpha_1,\dots,\alpha_{p^n}\}$である.よって$\alpha_1,\dots,\alpha_{p^n}$が相異なることを示せばよい.上の式の両辺を微分すると,$\bF_p$において$p^n=0$なので
$$ -1 = \sum_{i=1}^{p^n}\prod_{j\neq i}(x-\alpha_j) $$
となる.この式に$x=\alpha_i$を代入すると
$$ \prod_{j\neq i}(\alpha_i-\alpha_j) = -1 $$
となるので,$\alpha_1,\dots,\alpha_{p^n}$が相異なることがわかる.

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

有限体の包含関係

$\F_{p^n}\subset \F_{p^m}\iff n\mid m$.

$n\mid m$ならば$\F_{p^n}\subset \F_{p^m}$であることは定義から明らかである.逆に$\F_{p^n}\subset \F_{p^m}$であると仮定して$n\mid m$を示そう.$n$を割り切る素冪$l^k$に対して$l^k\mid 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\mid m$が得られる.

命題7より,小さい$n$に対する$\F_{p^n}$の包含関係は以下のようになっている(矢印は包含写像):
$$ \xymatrix{ \F_{p^4}&\F_{p^6}\\ \F_{p^2}\ar[u]\ar[ur]&\F_{p^3}\ar[u]&\F_{p^5}\\ &\F_p\ar[u]\ar[ul]\ar[ur] } $$

次数の求め方

具体的な$\bF_p$の元の次数を求めるには,以下の命題を用いるのが便利である:

$f(x)$$\F_p$係数の$n$次多項式とし,$\alpha$$\bF_p$における$f(x)$の根とする.$f(x)$$\F_p$上既約($\F_p$係数の範囲でこれ以上因数分解できない)ならば,$\alpha$の次数は$n$であり,$\bF_p$における$f(x)$の根は$\alpha,\alpha^p,\alpha^{p^2},\dots,\alpha^{p^{n-1}}$である.

$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0\;(a_i\in \F_p)$とする.$\beta\in \bF_p$$f(x)$の根ならば
$$ a_d\beta^d+a_{d-1}\beta^{d-1}+\cdots+a_1\beta+a_0 = 0 $$
であるが,両辺にFrobenius写像を適用すると,$a_i^p=a_i$より
$$ a_d\beta^{dp}+a_{d-1}\beta^{(d-1)p}+\cdots+a_1^p\beta+a_0 = 0 $$
となるので,$\beta^p$$f(x)$の根である.つまり,$\bF_p$における$f(x)$の根全体の集合を$S$とすると,写像$F\colon S\to S;\;F(x)=x^p$が定まる.$F$は単射なので全単射である.$F^k(\alpha)=\alpha$となる正整数$k$のうち最小のものを取る.$T=\{\alpha,\alpha^p,\dots,\alpha^{p^{k-1}}\}$と定めると,$F$は全単射$T\to T$に制限できる.
$$ g(x)=a_d\prod_{\beta\in T} (x-\beta) $$
と定めると,$g(x)$の係数はFrobenius写像で不変なので,$g(x)$$\F_p$係数多項式となる.定義より$g(x)$$f(x)$を割り切るので,$f(x)$が既約であるという仮定より$g(x)=f(x)$となる.よって$k=n,\;T=S$である.

Fibonacci数列への応用

有限体の応用例として,Fibonacci数の$\bmod p$での振る舞いについて調べる.Fibonacci数列は
$$ F_1=F_2=1,\quad F_{n+2}=F_{n+1}+F_n $$
により定まる数列であり,その一般項は
$$ F_n=\dfrac{\phi^n-\overline{\phi}^n}{\phi-\overline{\phi}}\quad\left(\phi=\dfrac{1+\sqrt{5}}{2},\;\overline{\phi}=\dfrac{1-\sqrt{5}}{2}\right) $$
で与えられる.これの「$\bmod p$版」を考えよう.$\bF_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\pmod{5}$ならば$\sqrt{5}\in \F_p$である.
(4) $p\equiv 2,3\pmod{5},\;p\neq 2$ならば$\sqrt{5}\in \F_{p^2}\setminus\F_p$であり,$\sqrt{5}^p=-\sqrt{5}$である.

(1),(2)は明らかである.以下$p$$2,5$でないとする.平方剰余の相互法則より,$p\equiv 1,4\pmod{5}$ならば$p$$\bmod 5$で平方剰余であり,$p\equiv 2,3\pmod{5}$ならば$p$$\bmod 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$とする.$\bF_p$の元$\alpha,\beta$
$$ \alpha = \dfrac{1+\sqrt{5}}{2},\quad \beta = \dfrac{1-\sqrt{5}}{2} $$
により定める.また$\bF_p$の元$u_n$
$$ u_n = \dfrac{\alpha^n-\beta^n}{\alpha-\beta} $$
により定める.すると$u_1=1,\;u_2=\alpha+\beta=1$であり,また$\alpha^{n+2}=\alpha^{n+1}+\alpha^n$および$\beta^{n+2}=\beta^{n+1}+\beta^n$より
$$ u_{n+2} = u_{n+1} + u_n $$
が成り立つ.すなわち,$u_n$$F_n$$\bmod p$で考えたものに他ならない.これを用いると次のような事実が示せる.

素数$p\neq 2,5$に対して$F_{n+2p}=F_{n+p}+F_n\pmod{p}$が成り立つ.

$\alpha^2=\alpha+1$にFrobenius写像を適用すると$\alpha^{2p}=\alpha^p+1$となり,$\alpha^{n+2p}=\alpha^{n+p}+\alpha^n$が得られる.同様に$\beta^{n+2p}=\beta^{n+p}+\beta^n$も成り立つので,$u_{n+2p}=u_{n+p}=u_n$が得られる.

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

$p\equiv 1,4\pmod{5}$ならば命題9より$\alpha,\beta\in \F_p$なので$\alpha^{n+p-1}=\alpha^n,\;\beta^{n+p-1}=\beta^n$である.よって$u_{n+p-1}=u_n$が得られる.$p\equiv 2,3\pmod{5}$ならば命題9より$\alpha,\beta\in \F_{p^2}\setminus\F_p$であり,$\alpha^p=\beta,\;\beta^p=\alpha$である.よって
$$ \alpha^{n+p+1}=\alpha^n(\alpha\beta)=-\alpha^n $$
であり,同様に$\beta^{n+p+1}=-\beta^n$も成り立つので,$u_{n+p+1}=-u_n$が得られる.

投稿日:1026
更新日:1028
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

J_Koizumi
106
10156

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中