概要
Haskell上で有限体1を使って遊ぼうという記事です。
体って何？
元の集合$K$と、以下の性質を満たす乗算($a\cdot{b}$), 加算($a+b$)の組$(K,\cdot,+)$を体と呼んでいます. なお, 乗算 $a\cdot{b}$ は演算子を省略して $ab$ と表記します.
- 加法が$K$の中で閉じていること: $\forall a,b\in{K}$, $a+b\in{K}$
- 乗法が$K$の中で閉じていること: $\forall a,b\in{K}$, $ab\in{K}$
- 加法の結合律: $\forall a,b,c\in{K}$, $(a+b)+c=a+(b+c)$
- 乗法の結合律: $\forall a,b,c\in{K}$, $(ab)c=a(bc)$
- 加法の交換律: $\forall a,b\in{K}$, $a+b=b+a$
- 乗法の交換律: $\forall a,b\in{K}$, $ab=ba$
- 分配律: $\forall a,b,c\in{K}$, $a(b+c)=ab+ac$, $(a+b)c=ac+bc$
- 加法単位元の存在: $\exists e\in{K}$, $\forall a\in{K}$, $e+a=a+e=a$
(以下、加法単位元を$0$と表記) - 乗法単位元の存在: $\exists e\in{K}$, $\forall a\in{K}$, $e\cdot{a}=a\cdot{e}=a$
(以下、乗法単位元を$1$と表記) - 加法逆元の存在: $\forall a\in{K}$, $\exists b\in{K}$, $a+b=b+a=0$
(以下、$a$の加法逆元を$-a$と表記) - 乗法逆元の存在: $\forall a\in{K}\setminus\{0\}$, $\exists b\in{K}$, $ab=ba=1$
(以下、$a$の乗法逆元を$a^{-1}$と表記)
私たちがよく知っている体の例としては, 有理数体$\mathbb{Q}$, 実数全体$\mathbb{R}$, 複素数体$\mathbb{C}$などがあります.
有限体
例として挙げた$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$は元の数(位数)が無限個ある体ですが、有限個の元しかもたない($\equiv$ 位数が有限であるような)体のことを有限体と呼びます.
有限体の位数は常に素数$p$か, $p$のべき乗$p^n$ $(n=1,2,\dots)$ になることが知られています(ここでは証明はしません). また, 位数が素数$p$であるような体を素体2と呼びます.
有限体の例として, 剰余環3$\mathbb{Z}_5$がなす体を考えます.
乗算:
- $1\cdot{0}\equiv{0}\ (\mathrm{mod} 5)$, $1\cdot{1}\equiv{1}\ (\mathrm{mod} 5)$, $1\cdot{2}\equiv{2}\ (\mathrm{mod} 5)$, $\dots$
- $2\cdot{0}\equiv{0}\ (\mathrm{mod} 5)$, $2\cdot{1}\equiv{2}\ (\mathrm{mod} 5)$, $2\cdot{2}\equiv{4}\ (\mathrm{mod} 5)$, $2\cdot{3}\equiv{1}\ (\mathrm{mod} 5)$, $2\cdot{4}\equiv{3}\ (\mathrm{mod} 5)$
- $\dots$
- $\dots$ , $4\cdot{3}\equiv{2}\ (\mathrm{mod} 5)$, $4\cdot{4}\equiv{1}\ (\mathrm{mod} 5)$
加算:
- $1+0\equiv{1}\ (\mathrm{mod} 5)$, $1+1\equiv{2}\ (\mathrm{mod} 5)$, $1+2\equiv{3}\ (\mathrm{mod} 5)$, $\dots$
- $2+0\equiv{2}\ (\mathrm{mod} 5)$, $2+1\equiv{3}\ (\mathrm{mod} 5)$, $2+2\equiv{4}\ (\mathrm{mod} 5)$, $2+3\equiv{0}\ (\mathrm{mod} 5)$, $2+4\equiv{1}\ (\mathrm{mod} 5)$
- $\dots$
- $\dots$ , $4+3\equiv{2}\ (\mathrm{mod} 5)$, $4+4\equiv{3}\ (\mathrm{mod} 5)$
これを表にすると以下のようになります.
| $\cdot$ | 0 | 1 | 2 | 3 | 4 | $+$ | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 0 | |
| 2 | 0 | 2 | 4 | 1 | 3 | 2 | 2 | 3 | 4 | 0 | 1 | |
| 3 | 0 | 3 | 1 | 4 | 2 | 3 | 3 | 4 | 0 | 1 | 2 | |
| 4 | 0 | 4 | 3 | 2 | 1 | 4 | 4 | 0 | 1 | 2 | 3 |
この演算規則の上で, 例えば分配律が成り立つかどうか確認してみましょう.
\begin{align}
2\cdot(3+4) &= 2\cdot{2} = 4 \\
2\cdot{3}+2\cdot{4} &= 1 + 3 = 4 \\
\therefore 2\cdot(3+4) &= 2\cdot{3}+2\cdot{4}
\end{align}
Haskellで有限体を使う
Haskell上で有限体を扱うライブラリとしては, finite-field があります. 現段階では素体 $\mathbb{Z}_p$ にしか対応していませんが, 有限体をHaskell上の Num クラスの型として扱うための仕組みが一通り実装されています.
とりあえず cabal を使ってインストールします(sandbox を使います).
$ mkdir sandbox
$ cd sandbox/
$ cabal update
Downloading the latest package list from hackage.haskell.org
$ cabal get finite-field
Unpacking to finite-field-0.9.0/
$ cd finite-field-0.9.0/
$ cabal sandbox init
Writing a default package environment file to
.../sandbox/finite-field-0.9.0/cabal.sandbox.config
Creating a new sandbox at
.../sandbox/finite-field-0.9.0/.cabal-sandbox
$ cabal install --only-dependencies
Resolving dependencies...
Notice: installing into a sandbox located at
.../sandbox/finite-field-0.9.0/.cabal-sandbox
(snip)
$ cabal configure
Resolving dependencies...
Configuring finite-field-0.9.0...
$
実験のために repl(ghci)を立ち上げましょう. finite-field では素体 $\mathbb{Z}_p$ に対応する型を作るのに TemplateHaskell を使うので, 必要なオプションを指定します.
$ cabal repl --ghc-options="-XTemplateHaskell -XDataKinds"
Preprocessing library finite-field-0.9.0...
GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help
[1 of 3] Compiling Data.FiniteField.Base ( src/Data/FiniteField/Base.hs, interpreted )
[2 of 3] Compiling Data.FiniteField.PrimeField ( src/Data/FiniteField/PrimeField.hs, interpreted )
[3 of 3] Compiling Data.FiniteField ( src/Data/FiniteField.hs, interpreted )
Ok, modules loaded: Data.FiniteField, Data.FiniteField.Base, Data.FiniteField.PrimeField.
*Data.FiniteField>
素体$\mathbb{Z}_5$を定義してみます. 位数$p$の素体を表す型はTemplateHaskellと型レベル自然数を使った $(primeField p) という式で定義できます. (実際の型は PrimeField n になります)
> type F5 = $(primeField 5)
> let a = 2 :: F5
> let b = 3 :: F5
> let c = 4 :: F5
さっき確認した分配律をここでも確認してみましょう.
> a*(b + c)
4
> a*b + a*c
4
>
PrimeField a 型は Fractional クラスのインスタンスにもなっているので, 1/x で逆数(乗法逆元)を求めることもできます.
> let d = 1/a
> d
3
> a*d
1
>
フェルマーの小定理4を実験的に確認してみましょう. 素数 $p=104561$ を法としたとき, $p$ と互いに素な整数 $a$ について, $a^{p-1}$ が $1$ になることを確かめてみます.
> let p = 104561
> type Fp = $(primeField p)
> let a = 123 :: Fp
> a^(p-1)
1
> let xs = [1..(p-1)] :: [Fp]
> map (^(p-1)) xs
[1,1,1,1,1,1,1,1,1, ... ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
>
体上の乗法群
位数$p$の有限体$K$について, 適切な元$\alpha\in{K}$をとると, 乗法群$\{1,\alpha,\alpha^2,\dots\}$は$\alpha$を生成元とした位数$p-1$の巡回群5になります.
実験的に確かめてみましょう.
> type F17 = $(primeField 17)
> let a = 3 :: F17
> take 33 $ iterate (a*) 1
[1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1]
> a^16
1
体$\mathbb{Z}_{17}$上で, $3^j$ $(j=0,1,\dots)$ によって$0$を除く全ての元を表すことができ, また,
3^{16} = 1
なので$16$乗で単位元に戻ってくる, 位数が$16=17-1$の巡回群を作ることができました.
生成元は唯一とは限りません. 試しに$7^j$ $(j=0,1,\dots)$を計算してみると,
> let b = 7 :: F17
> take 33 $ iterate (b*) 1
[1,7,15,3,4,11,9,12,16,10,2,14,13,6,8,5,1,7,15,3,4,11,9,12,16,10,2,14,13,6,8,5,1]
>
となり, $7$を生成元としても巡回群ができることがわかります.
まとまらない
体$K$上の多項式とか拡大体$\mathbb{F}(p^n)$とかそれらの応用の話もしようと思っていたのですが, ヘビーになりそうなので次の記事に送ります.
-
厳密には, 「素体」とは自分自身以外の部分体をもたない体のことです. ↩
-
参考: 有限巡回群 ［物理のかぎしっぽ］ ↩