Haskell上で有限体を使って遊ぶ

## 概要
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$ <br/>(以下、加法単位元を$0$と表記)
- 乗法単位元の存在: $\exists e\in{K}$, $\forall a\in{K}$, $e\cdot{a}=a\cdot{e}=a$ <br/>(以下、乗法単位元を$1$と表記)
- 加法逆元の存在: $\forall a\in{K}$, $\exists b\in{K}$, $a+b=b+a=0$ <br/>(以下、$a$の加法逆元を$-a$と表記)
- 乗法逆元の存在: $\forall a\in{K}\setminus\\{0\\}$, $\exists b\in{K}$, $ab=ba=1$ <br/>(以下、$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 |

この演算規則の上で, 例えば分配律が成り立つかどうか確認してみましょう.

```math
\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](https://hackage.haskell.org/package/finite-field "finite-field: Finite Fields") があります. 現段階では素体 $\mathbb{Z}_p$ にしか対応していませんが, 有限体をHaskell上の `Num` クラスの型として扱うための仕組みが一通り実装されています.

とりあえず `cabal` を使ってインストールします(sandbox を使います).

```shell-session
$ 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 を使うので, 必要なオプションを指定します.

```shell-session
$ 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` になります)

```haskell
> type F5 = $(primeField 5)
> let a = 2 :: F5
> let b = 3 :: F5
> let c = 4 :: F5
```

さっき確認した分配律をここでも確認してみましょう.

```haskell
> a*(b + c)
4
> a*b + a*c
4
>
```

`PrimeField a` 型は `Fractional` クラスのインスタンスにもなっているので, `1/x` で逆数(乗法逆元)を求めることもできます.

```haskell
> let d = 1/a
> d
3
> a*d
1
>
```

フェルマーの小定理[^4]を実験的に確認してみましょう. 素数 $p=104561$ を法としたとき, $p$ と互いに素な整数 $a$ について, $a^{p-1}$ が $1$ になることを確かめてみます.

```haskell
> 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]になります.

実験的に確かめてみましょう.

```haskell
> 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$を除く全ての元を表すことができ, また, 

```math
3^{16} = 1
```

なので$16$乗で単位元に戻ってくる, 位数が$16=17-1$の巡回群を作ることができました.
生成元は唯一とは限りません. 試しに$7^j$ $(j=0,1,\dots)$を計算してみると,

```haskell
> 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)$とかそれらの応用の話もしようと思っていたのですが, ヘビーになりそうなので次の記事に送ります.


[^1]: 参考: [体に関する基本的なこと ［物理のかぎしっぽ］](http://hooktail.sub.jp/algebra/FieldBasic/ "体に関する基本的なこと [物理のかぎしっぽ]")
[^2]: 厳密には, 「素体」とは自分自身以外の部分体をもたない体のことです.
[^3]: 参考: [Quotient Ring -- from Wolfram MathWorld](http://mathworld.wolfram.com/QuotientRing.html "Quotient Ring -- from Wolfram MathWorld")
[^4]: 参考: [Fermat's Little Theorem -- from Wolfram MathWorld](http://mathworld.wolfram.com/FermatsLittleTheorem.html "Fermat's Little Theorem -- from Wolfram MathWorld")
[^5]: 参考: [有限巡回群 ［物理のかぎしっぽ］](http://hooktail.sub.jp/algebra/FiniteCyclicGroup/ "有限巡回群 [物理のかぎしっぽ]")