Haskell
数学
信号処理
代数学

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$
    (以下、加法単位元を$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

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

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}

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


  1. 参考: 体に関する基本的なこと [物理のかぎしっぽ] 

  2. 厳密には, 「素体」とは自分自身以外の部分体をもたない体のことです. 

  3. 参考: Quotient Ring -- from Wolfram MathWorld 

  4. 参考: Fermat's Little Theorem -- from Wolfram MathWorld 

  5. 参考: 有限巡回群 [物理のかぎしっぽ]