#9 有限体
今回は、有限体の基礎的な事項を確認する。 いくつかの定理の証明を省略しているが、気になる方は代数学の教科書(書名に「ガロア理論」が含まれるものを読むと良いだろう)を参照されたい。
有限体ことはじめ
体
体 (field) は、ざっくり言うと四則演算ができる数の体系である。 より具体的に言うと、加法 + と乗法 \times が定まった集合 K が体であるとは、
- 加法 + について、 K が可換群となる。つまり、
- 結合法則:任意の a,b,c\in K について (a+b)+c=a+(b+c).
- 交換法則:任意の a,b\in K について a+b=b+a.
- 単位元:加法の単位元 0\in K があって、任意の a\in K について a+0=0+a=a.
- 逆元:任意の a\in K に対してある b\in K が存在し、 a+b=b+a=0. この b は通常 -a と表記される。
- 乗法 \times について、 K が可換モノイドとなる。つまり、
- 結合法則:任意の a,b,c について (a b) c=a (b c).
- 交換法則:任意の a,b\in K について a b=b a.
- 単位元:乗法の単位元 1\in K があって、任意の a\in K について a\cdot 1=1\cdot a=a.
- 乗法 \times について、 0 以外の元が逆元(逆数)を持つ。a の逆元は a^{-1} や 1/a と表記される。
- 1\ne 0.
- 分配法則:任意の a,b,c\in K に対して、 a(b+c)=ab+ac, (a+b)c=ac+bc.
が成り立つことを言う。
例 有理数の全体 \mathbb{Q} は体をなす。
例 実数の全体 \mathbb{R} は体をなす。
例 複素数の全体 \mathbb{C} は体をなす。
例 代数的実数の全体は体をなす。
例 代数的数の全体 \overline{\mathbb{Q}} は体をなす。
例 体 K 上の有理関数の全体 K(x) は体をなす。
例 整数の全体 \mathbb{Z} は体ではない。 除算が自由に行えないからである。 例えば、 2\in\mathbb{Z} の乗法に関する逆元は \mathbb{Z} の中には存在しない。
例 \mathbb{Z}/2\mathbb{Z}=\{0,1\} に、和と積を次のように定める: \begin{aligned} 0+0&=0, & 0\cdot 0&=0, \\ 0+1&=1, & 0\cdot 1&=0, \\ 1+0&=1, & 1\cdot 0&=0, \\ 1+1&=0, & 1\cdot 1&=1. \end{aligned} この時、 \mathbb{Z}/2\mathbb{Z} は足し算の逆元を持つし、 0 以外の数(つまり、 1)に関して積の逆元を持つので、体となる。 この体は \mathbb{F}_2 と表記される。
例 \mathbb{Z}/3\mathbb{Z}=\{0,1,2\} に、和と積を次のように定める:
- \mathbb{Z}/3\mathbb{Z} としての和 a+b は、通常の整数として計算した a+b を3で割った余りとする。
- \mathbb{Z}/3\mathbb{Z} としての積 ab は、通常の整数として計算した ab を3で割った余りとする。
計算例:1+1=2,1+2=0,2+2=1,1\cdot2=2,2\cdot2=1.
この時、 \mathbb{Z}/3\mathbb{Z} は和に関する逆元 {-0}=0,{-1}=2,{-2}=1 を持ち、0以外の元について積に関する逆元 1^{-1}=1,2^{-1}=2 を持つので、体となる。 この体は \mathbb{F}_3 と表記される。
例 一般に、2以上の自然数 m について、 \mathbb{Z}/m\mathbb{Z}=\{0,1,2,\ldots,m-1\} に、和と積を次のように定める:
- \mathbb{Z}/m\mathbb{Z} としての和 a+b は、通常の整数として計算した a+b を m で割った余りとする。
- \mathbb{Z}/m\mathbb{Z} としての積 ab は、通常の整数として計算した ab を m で割った余りとする。
この時、 \mathbb{Z}/m\mathbb{Z} は m が素数の時、かつその時に限り体となる。 つまり、 1,\ldots,m-1 の全てが積の逆元を持つことと、 m が素数であることが同値である。 素数 p についての \mathbb{Z}/p\mathbb{Z} を \mathbb{F}_p と書く。
例 \mathbb{Z}/4\mathbb{Z}=\{0,1,2,3\} は体にはならない。 2が逆元を持たない、つまり 0\cdot 2=0,1\cdot 2=2,2\cdot 2=0,3\cdot 2=2 より、 a\cdot 2=1 となるような a が存在しないからである。
例 \mathbb{Z}/5\mathbb{Z}=\{0,1,2,3,4\} は、5が素数なので体である。これを \mathbb{F}_5 と書く。
演習問題 \mathbb{F}_5 において、多項式 x^2-2 の値を、 x=0,1,2,3,4 について計算せよ。
演習問題 \mathbb{F}_5 において、多項式 x^2+x+3 の値を、 x=0,1,2,3,4 について計算せよ。
演習問題 \mathbb{F}_5 において、多項式 x^5 の値を、 x=0,1,2,3,4 について計算せよ。
例 \mathbb{F}_5 の元の2つ組からなる集合 K=\{(a,b)\mid a,b\in\mathbb{F}_5\} に対して、演算を次のように定める:
- 加法:(a,b)+(c,d)=(a+c,b+d)
- 乗法:(a,b)\cdot(c,d)=(ac+2bd,ad+bc)
- 乗法の逆元:(a,b)^{-1}=\left(\frac{a}{a^2-2b^2},\frac{-b}{a^2-2b^2}\right)
この時、この K は体となる。 この時の K の元 (a,b) を a+b\sqrt{2} と書き、 K を \mathbb{F}_5(\sqrt{2}) と書く。 \mathbb{F}_5(\sqrt{2}) は25個の元からなる。
体について標数 (characteristic) と呼ばれる整数が定まる。 さっき紹介した \mathbb{F}_2 や \mathbb{F}_3 は、 1 を何回か足すと 0 になってしまう。 \mathbb{F}_2 においては 1+1=0 だし、 \mathbb{F}_3 においては 1+1+1=0 となる。 体 K において 1 を n 回足した時にはじめて 0 となった場合、体 K の標数は n であるという。 1 を何回足しても 0 とならない場合(そのような正の自然数 n が存在しない場合)は、その体の標数は 0 であるという。
例えば、\mathbb{F}_2 の標数は 2 で、\mathbb{F}_3 の標数は 3 である。 \mathbb{F}_5 と \mathbb{F}_5(\sqrt{2}) の標数はいずれも 5 である。 \mathbb{Q} や \mathbb{R} の標数は 0 である。
定理. 体の標数が正の場合、それは素数である。
証明. 体 K の標数が合成数 nm, n>1,m>1 だったとする。
体 K において 1 を n 回足したものを \overline{n}、 1 を m 回足したものを \overline{m} と書くことにする。
n は K の標数である nm よりも小さいので、 \overline{n}\ne 0 である。 m についても同様に、 \overline{m}\ne 0 である。 一方、体の標数は nm なので、 \overline{n}\cdot\overline{m}=\overline{nm}=0 である。
\overline{n} は 0 でないので、積に関しての逆元 a=\overline{n}^{-1} を持つ。 すると、 0\ne \overline{m}=(a\overline{n})\overline{m}=a(\overline{n}\cdot\overline{m})=a\cdot 0=0 となり、矛盾。
よって、体 K の標数は素数である。
体の基礎となる集合が有限個の場合、特に有限体という。 有限体でない体を無限体という。 先の例では、 \mathbb{F}_2, \mathbb{F}_3, \mathbb{F}_5, \mathbb{F}_5(\sqrt{2}) が有限体である。
有限体ならば標数は正だが、標数が正だからといって有限体とは限らない。 有限体上の有理関数体 \mathbb{F}_p(x) や、有限体の代数閉包 \overline{\mathbb{F}_p} は無限体である。
群
群は、二項演算(ここでは中点 \cdot で書く)が定義された集合であって、次の性質を満たすもののことである。
- 結合則:任意の x,y,z に対して、 (x\cdot y)\cdot z=x\cdot(y\cdot z).
- 単位元の存在:ある元 e が存在して、任意の x に対して e\cdot x=x\cdot e=x を満たす。 このような元 e は存在すればただ一つであり、単位元と呼ばれる。
- 逆元の存在:各 x に対して、ある y が存在して、 x\cdot y=y\cdot x=e となる。 それぞれの x に対して、このような y は存在すればただ一つであり、 x^{-1} と表記される。
群の例は色々ある。
例 整数の全体 \mathbb{Z} は加法について群をなす。
例 2以上の自然数 m に関して、 \mathbb{Z}/m\mathbb{Z} は加法について群をなす。m が素数である必要はない。
例 体 K は加法について群をなす。
例 体 K からゼロを除いた集合 K\setminus\{0\} は、乗法に関して群をなす。 この群は体 K の乗法群と呼ばれ、 K^\times と書かれる。
例 n 本の縦線からなるあみだくじの全体について、縦に繋げるという操作が考えられる。 「n 本の縦線からなるあみだくじの全体」はこの操作に関して群をなす:
- この操作は結合的である。
- 横線が1本も入っていないあみだくじは、この操作に関して単位元となる。
- あみだくじを上下にひっくり返せば、逆元が得られる。
集合として有限集合な群は、有限群と呼ばれる。 \mathbb{Z}/m\mathbb{Z} は有限群であるし、有限体 K を加法について見るとこれは有限群である。 有限体 K の乗法群も有限群である。
群 G の元の個数を位数といい、集合の元の個数と同じ \#G で表記する。 群が無限個の元からなる場合は位数が無限であるという。 \mathbb{Z}/m\mathbb{Z} は位数 m の有限群である。
演算が可換な群は可換群と呼ばれる。 \mathbb{Z} や \mathbb{Z}/m\mathbb{Z} は可換群である。 体の加法と乗法は可換なので、 K と K^\times はそれぞれ可換群である。 あみだくじの例では n\le 2 の場合は可換群だが、 n\ge 3 の場合は非可換群となる。
群 G の部分集合 H が、 G と同じ演算について群をなす場合、 H は G の部分群であるという。 「同じ演算について」という部分がポイントである。 体 K について、 K と K^\times はどちらも群となり、 K^\times=K\setminus\{0\} は K の部分集合だが、 K と K^\times では考えている演算が違うため、 K^\times は K の部分群ではない。
群 G について、適当な a\in G を使うと G の任意の元が a の冪 a^i として書けてしまう、つまり G=\{\ldots,a^{-2},a^{-1},e,a,a^2,\ldots\} が成り立つ、という状況がある。 このような a は G の生成元であるといい、一個の元で生成される群を巡回群と呼ぶ。 群の結合法則より、巡回群は可換群である。
例 \mathbb{Z} や \mathbb{Z}/m\mathbb{Z} は巡回群である。どちらも、 1 によって生成される。
例 加法についての群 \mathbb{F}_5(\sqrt{2}) は巡回群ではない。
群 G の元 a について、 \{a^i\mid i\in\mathbb{Z}\}=\{\ldots,a^{-2},a^{-1},e,a,a^2,\ldots\} という集合を考えると、これは G の部分群となる。 これを a の生成する巡回群と呼び、 \langle a\rangle と表記する。 \langle a\rangle の位数を、元 a の位数と呼ぶ。
例 \mathbb{Z}/6\mathbb{Z} の元 2 が生成する巡回群は、 \{0,2,4\} である。 よって、元 2 の位数は 3 である。
補題. 有限群 G の部分群 H の位数は、 G の位数の約数である。
証明. 商集合 G/H=\{xH\mid x\in G\} を考える。
群の性質より、それぞれの同値類の元の個数は等しい:\#(xH)=\#(yH)
よって \#G=\#(G/H)\cdot \#H と書け、 \#H は \#G の約数である。
定理.G を位数 n の有限群とする。 この時、任意の x\in G について、 x^n=e.
証明. G の元の、長さ n+1 の列 e,x,x^2,x^3,\ldots,x^{n-1},x^n を考える。
この時、ある自然数 0<k\le n に対して x^k=e となる。 (理由: この群の位数は n なので、長さ n+1 の列に対しては少なくとも1組は等しい元の組が存在する。 つまり、 x^i=x^j となる i<j が存在する。 この両辺に x^{-i} をかけると、 e=x^{j-i} を得る。)
そのような k として最小のものを選ぶと、 k は x の位数であり、 x^k=e となる。 一方、 \langle x\rangle は G の部分群なので、 \langle x\rangle の位数 k は n の約数である。 つまり、適当な整数 l によって n=kl と書ける。 よって、 x^n=x^{kl}=\left(x^k\right)^l=e^l=e. \qedhere
素体
いくつかの体に関しては、 \mathbb{Q}\subset\mathbb{R}\subset\mathbb{C} という包含関係が成り立つ(この際、加法、乗法は同じものを使う)。 このような包含関係の中で最小のものを素体 (prime field) と呼ぶ。
有理数体 \mathbb{Q} は、素体である。 なぜなら、任意の有理数は 1 と四則演算を使って作り出すことができる(例:3/4=(1+1+1)/(1+1+1+1)))。 よって、 \mathbb{Q} からいくつか元を取り除いて \mathbb{Q} よりも小さい体を作ることはできない。
素数 p について、 p 個の元 \{0,1,\ldots,p-1\} からなる有限体 \mathbb{F}_p も、素体である。 標数 p の体は必ず \mathbb{F}_p を素体として含む。
素体は、標数ごとにただ1つ存在する。 \mathbb{Q} は標数 0 の素体であり、標数 0 の体は必ず \mathbb{Q} を部分体として含む。
代数拡大
体 K を固定して考えると、 K 上のある種の代数方程式は K 上に根を持たない。
例えば、 \mathbb{R} 上の方程式 x^2+1=0 は実根を持たないし、 \mathbb{Q} 上の代数方程式 x^2-2=0 は有理数根を持たない。 \mathbb{F}_2 上の多項式 x^2+x+1=0 は \mathbb{F}_2 に根を持たないし、 \mathbb{F}_3 上の多項式 x^2+1=0 は \mathbb{F}_3 上に根を持たない。
そういう時、もとの体にその方程式の根となるような元 \alpha を付け加えてやることができる。
その付け加えた体を、 K の代数拡大体と呼び、 K(\alpha) と書く。
数学的に真面目にやるには、 K の多項式環 K[x] をその既約多項式 f(x) の生成するイデアル (f) で割る、という操作をする。 そうして得られたもの K[x]/(f) は再び体となる。
有限体
元の個数が有限である体を有限体 (finite field) という。
有限体の標数は正である。 なぜなら、標数 0 の体は素体として有理数体 \mathbb{Q} を含み、これは無限体であるからである。
有限体の例としては、標数 p の素体 \mathbb{F}_p がある。
他の例は、 \mathbb{F}_p を代数拡大することによって得られる。 体の例として最初の方に挙げた \mathbb{F}_5(\sqrt{2}) は有限体である。
例えば、 \mathbb{F}_3 には 2 の平方根がない(対比:\mathbb{R} には -1 の平方根がない)。 2の平方根を付け足したものは \mathbb{F}_3(\sqrt{2})=\{a+b\sqrt{2}\mid a,b\in\mathbb{F}_3\} となり、これは 9 個の元からなるので有限体である。
逆に、有限体は必ず \mathbb{F}_p の代数拡大として書ける。
定理. 有限体 K の位数 q は、ある素数 p と 1 以上の整数 e によって p^e と書ける。
証明. K の標数を p とする。 K は \mathbb{F}_p の拡大体である。 K は \mathbb{F}_p 上のベクトル空間であり、 \#K は有限なので、 \dim_{\mathbb{F}_p} K=n とおけば \#K=p^n である。
定理.K を位数 n の有限体とする。 この時、任意の x\in K について、 x^n=x.
証明. x=0 の時は明らか。
x\ne 0 の時を考える。 K は体なので x は可逆であり、 x\in K^\times である。 K^\times は位数 n-1 の有限群であり、先の定理を適用すれば x^{n-1}=1 を得る。 この両辺に x をかければ、欲しい等式が得られる。
系(フェルマーの小定理).素数 p について、 x^p\equiv x \pmod{p}.
この連載では、一般の有限体の場合についての定理を単に「フェルマーの小定理」と呼ぶことにする。
定理. 有限体の乗法群 \mathbb{F}_q^\times は巡回群となる。
この定理はここでは証明しない。代わりに、いくつか例を見てみる。
例 \mathbb{F}_5^\times=\{1,2,3,4\} を考える。 2^0=1,2^1=2,2^2=4,2^3=8=3 なので、 \mathbb{F}_5^\times は 2 によって生成される。
例 \mathbb{F}_3(\sqrt{2})^\times=\{1,2,\sqrt{2},1+\sqrt{2},2+\sqrt{2},2\sqrt{2},1+2\sqrt{2},2+2\sqrt{2}\} を考える。 \begin{aligned} (2+\sqrt{2})^0&=1, & (2+\sqrt{2})^1&=2+\sqrt{2}, & (2+\sqrt{2})^2&=\sqrt{2}, \\ (2+\sqrt{2})^3&=2+2\sqrt{2}, & (2+\sqrt{2})^4&=2, & (2+\sqrt{2})^5&=1+2\sqrt{2}, \\ (2+\sqrt{2})^6&=2\sqrt{2}, & (2+\sqrt{2})^7&=1+\sqrt{2} \end{aligned} となるので、 \mathbb{F}_3(\sqrt{2})^\times は 2+\sqrt{2} によって生成される。
標数 p (p>0) の体において、 p 乗する写像 x\mapsto x^p は体の準同型写像となる。 つまり、 \varphi\colon x\mapsto x^p について、
- \varphi(1)=1,
- \varphi(x+y)=\varphi(x)+\varphi(y),
- \varphi(xy)=\varphi(x)\varphi(y)
が成り立つ。 1. と 3. は明らかだろう。 2. は、つまり (x+y)^p=x^p+y^p だが、これは mod p で \binom{p}{k}\equiv\begin{cases} 1 & (k=0 \text{ または } p) \\ 0 & (\text{それ以外}) \end{cases} から従う。 この「p 乗する」写像を、フロベニウス写像という。 有限体の場合は、この写像は同型写像となる。
定理. 有限体 K は位数 q=\#K のみによって一意に決まる。 つまり、元の個数が等しい有限体は全て同型である。
この定理も証明は省略する。 この定理により、位数 q の有限体は同型を除いて一意なので、それを \mathbb{F}_q と書く。
例 \mathbb{F}_5 には 2 と 3 の平方根がない。 先ほど \mathbb{F}_5 に 2 の平方根を添加したもの \mathbb{F}_5(\sqrt{2}) を取り上げたが、実はこの時点ですでに 3 の平方根も含まれている: (\pm 2\sqrt{2})^2=3 つまり、 \mathbb{F}_5(\sqrt{2}) は 3 の平方根を持つ。 逆に、 \mathbb{F}_5 に 3 の平方根を添加したもの \mathbb{F}_5(\sqrt{3}) は、 2 の平方根を含む。 よって、 \mathbb{F}_5(\sqrt{2})\cong\mathbb{F}_5(\sqrt{3}) で、これを \mathbb{F}_{5^2} と書く。
Haskell における有限体の実装
これまでは、具体的な環や体などの数学的対象に、 Haskell の型を対応させてきた。 しかし、有限体 \mathbb{F}_q という対象は q という整数に依存する。
個々の有限体に対して、 \mathbb{F}_2 には型 F2
を, \mathbb{F}_3 には型 F3
を、というに個別の型を作ることはもちろんできる。 実行時に与えられる素数 p に対して \mathbb{F}_p に対応する型を作るにはどうすればいいか。
項に依存した型は依存型 (dependent types) と呼ばれるが、(古典的には) Haskell には依存型はない。 しかし、自然数を型でエンコードすることはできて、あとはランク2多相 (rank-2 polymorphism) があれば、実行時に与えられた自然数を型レベルに持ち上げることができる。 型レベルに持ち上げた自然数から実行時に使える値を取り出すのには型クラスを使えば良い、というのが以下の論文で述べられている:
- Oleg Kiselyov and Chung-chien Shan, Functional Pearl: Implicit Configurations – or, Type Classes Reflect the Values of Types
これを Haskell のライブラリーとして実装したのが reflection パッケージである。 ただし、型レベル自然数としては通常の型ではなくて Nat
カインドの型を使うし、実行時に与えられた自然数を型レベルに持ち上げる操作には多相再帰ではなく GHC の実装を悪用したものになっている。
さて、この連載は一変数多項式から始まり、(多倍長演算を除けば)なるべく自前で各種アルゴリズムを実装するようにしてきた。 しかし、有限体に関しては、(和、差、積に関しては)誰が実装しても同じような実装になると考えられ、自前で実装する意義は薄いと考えられる。 よって、ここでは有限体を再発明することはせず、既存の実装である finite-field パッケージをそのまま利用することにする。
finite-field パッケージの使い方を簡単に確認しておく。 finite-field パッケージが提供する型や関数は、 Data.FiniteField
モジュールを import することによって使えるようになる。
Data.FiniteField
モジュールは、有限体を表す型クラス FiniteField
と、有限素体を表すデータ型 PrimeField
, それに有限素体の元を整数に変換する関数 toInteger
を提供している:
class Fractional k => FiniteField k where
order :: k -> Integer
char :: k -> Integer
pthRoot :: k -> k
allValues :: [k]
data PrimeField (p :: Nat) = ...
toInteger :: PrimeField p -> Integer
FiniteField
のメソッドを一応説明しておく。 order
は有限体の位数、つまり元の個数だ。 char
は有限体の標数、 pthRoot
は p 乗根を返す。allValues
は有限体の元をリストとして返す。
【2018年3月6日 追加】PrimeField
型も IntegralDomain
と GCDDomain
のインスタンスにしておこう:
module Numeric.AlgebraicReal.Class where
import Data.Ratio
import qualified Data.Vector as V
import Data.FiniteField
import GHC.TypeLits (KnownNat)
-- 略
instance (KnownNat p) => IntegralDomain (PrimeField p) where
= (/)
divide
instance (KnownNat p) => GCDDomain (PrimeField p) where
= fieldGcd
gcdD = fieldContentV contentV
finite-field パッケージを使うために、algebraic-real.cabal の build-depends:
に次のように書き加える:
build-depends: base >= 4.7 && < 5
, vector
, finite-field
stack.yaml の extra-deps:
にも追加する:
# Dependency packages to be pulled from upstream that are not in the resolver
# (e.g., acme-missiles-0.3)
extra-deps:
- finite-field-0.9.0
それができたら stack repl
で ghci を起動する。 プロンプトに :m Data.FiniteField
と打ち込んでコンテクストを切り替え、:set -XDataKinds
で DataKinds 拡張を有効にする。 DataKinds拡張は、型レベルの自然数を普通に記述するために必要となる。
*Numeric.AlgebraicReal.UniPoly Numeric.AlgebraicReal.AlgReal Numeric.AlgebraicReal.CReal Numeric.AlgebraicReal.Class Numeric.AlgebraicReal.Factor.Kronecker Numeric.AlgebraicReal.Factor.SquareFree Numeric.AlgebraicReal.Interval Numeric.AlgebraicReal.Resultant Numeric.AlgebraicReal.UniPoly> :m Data.FiniteField
Prelude Data.FiniteField> :set -XDataKinds
計算例として、 \mathbb{F}_{11} において x^{11}=x となることを確かめてみよう。
Prelude Data.FiniteField> 2^11 :: PrimeField 11
2
Prelude Data.FiniteField> 3^11 :: PrimeField 11
3
Prelude Data.FiniteField> 4^11 :: PrimeField 11
4
有限体上の多項式の計算もしてみよう。 まず :m + Numeric.AlgebraicReal.UniPoly
で UniPoly
モジュールを使えるようにする。
Prelude Data.FiniteField> :m + Numeric.AlgebraicReal.UniPoly
Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly>
(x+1)^{11}=x^{11}+1 となることを確認してみよう。
Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly> (ind + 1)^11 :: UniPoly (PrimeField 11)
UniPoly [1,0,0,0,0,0,0,0,0,0,0,1]
Prelude Data.FiniteField Numeric.AlgebraicReal.UniPoly> ((ind + 1)^11 :: UniPoly (PrimeField 11)) == ind^11 + 1
True
これで有限体についての準備が整ったので、次回からは有限体上の多項式の因数分解アルゴリズムを取り上げて行く。