Haskell で有限体を実装する
強力な型システムにより， Haskell ではかなり抽象的な概念を型クラスとして実装することができます． 例えば， 代数学における「体」もその例外ではありません． 今回は体を型クラスに， そのインスタンスとして有限体を実装してみました．
有限体とは
そもそも体とは， 簡単に言うと零元以外の任意の元が積に関する逆元を持つような可換環のことです． 例えば， 有理数・実数・複素数等が該当します． これら3つの集合は無限集合ですが， 有限集合の場合を特に「有限体」などと呼びます．
また， 体の要素の個数を標数とか呼びます．
実は， どんな標数についても有限体が存在するわけではありません． 一般に， 有限体の標数は素数のとき（素体）， もしくは素数の冪乗のとき（素体の拡大）に限ります．
なお， 本記事では標数 p を持つ有限体を \(\mathbb{F}_p\) と書きます．
このうち， 素体の場合は剰余環 \(\mathbb{Z} / p \mathbb{Z}\)により有限体を構成できます．
拡大体 \(\mathbb{F}_{p^n}\) は \(\mathbb{Z} / p \mathbb{Z}\) 上の多項式環 \(\mathbb{Z}_p [x]\) と \(n + 1\) 次の既約多項式 \(f (x)\) に対し， \(\mathbb{Z}_p [x] / < f (x) > \) で構成できます（つまり同型）．
今回は， さしあたり素体に絞って実装してみます．
体の実装
手始めに， 体を型クラスとして定義してみます．
class (Num k) => Field k where fRecip :: k -> Maybe k
可換環までの要件については， Num 型クラスのインスタンスであれば， 記述できます． よって， Num 型クラスのサブクラスにしておきます．
なお， Haskell には Fractional 型クラスという体のような型クラスが存在しますが， こちらは浮動小数点数を表すもので， 若干気持ちが異なる気がします．
ということで今回は， 逆元計算のみを要件とするシンプルな Field 型クラスを定義しました． 一般に零元の逆元は存在しないため， Maybe 型にくるんであげています．
有限体の実装
型定義
体を型クラスとして定義した上で， 有限体はそのインスタンスにしてあげます．
有限体 \(\mathbb{F}_p\) を F p 型とします．
newtype F (p :: Nat) = F Integer deriving (Eq, Ord)
フィールドは Integer です． つまり F p 型の値は， 一見すると整数のように振る舞います．
F p 型の定義では， まず (p :: Nat) で， 種の宣言をしています． これにより， 位数を自然数に制限できます． このように明示的に種の注釈を記述するには DataKinds や KindSignatures といった言語拡張が必要です．
インスタンス宣言
まず， 整数から F p 型を生成する関数を定義しておきます．
mkF :: KnownNat p => Integer -> F p mkF n | isPrime $ natVal r = r | otherwise = error "Required that p is prime." where r = F $ n `mod` natVal r
こいつを利用してインスタンス宣言を入れていきます．
instance KnownNat p => Show (F p) where show (F m) = show m instance KnownNat p => Num (F p) where (F m) + (F n) = mkF $ m + n (F m) - (F n) = mkF $ m - n (F m) * (F n) = mkF $ m * n negate (F m) = mkF $ - m abs = id signum (F m) | m == 0 = F 0 | otherwise = F 1 fromInteger = mkF instance KnownNat p => Field (F p) where fRecip a@(F m) | (mkF m :: F p) == 0 = Nothing | isPrime p = Just $ mkF s | otherwise = Nothing where (r, s, _) = eea m p p = natVal a
基本的には常に「p で割った余りを出力する」スタンスなので，
Field 型クラスのインスタンス宣言だけ簡単に触れます．
fRecip 関数ですが， まず 0 は逆元を持たないので Nothing を返します．
次に， 位数との GCD が1でない， つまり互素じゃないとき， 逆元は存在しません． 今回は剰余環で単純に構成できる素体に限って実装しているためです．
で， 肝心の存在する逆元ですが， 今回は EEA を用いて計算させています． ちなみに EEA の素朴な実装は次のようになります．
eea :: (Integral m) => m -> m -> (m, m, m) eea f g = loop (f, 1, 0) (g, 0, 1) where loop (r0, s0, t0) (r1, s1, t1) | r2 == 0 = (sg * r1, sg * s1, sg * t1) | otherwise = loop (r1, s1, t1) (r2, s2, t2) where sg = signum r1 (q, r2) = r0 `divMod` r1 s2 = s0 - s1 * q t2 = t0 - t1 * q
どうして EEA で求まるのか， 以下簡単な証明です．
\(m, p \in \mathbb{N}\) とする． EEA によって，
\begin{align*}
s m + t p = \gcd (m, p)
\end{align*}
なる \(s, t \in \mathbb{Z}\) を計算できる．\(p\) が素数ならば \(\gcd(m, p) = 1\) だから，
\begin{align*}
s m + t p = 1\
\end{align*}
ここで， \( p \equiv 0 \mod p\) より，
\begin{align*}
1 = s m + t p \equiv s m \mod p
\end{align*}
よって， \(s\) は \(\mathbb{F}_p\) における \(m\) の逆元となる．
ということです． 計算例を載せておきます．
>let a = 45 :: F 23 >let b = 45 :: F 29 >let c = 52 :: F 23 >(a, b, c) (22,16,6) -- a と b はともに45で定義したが，法が異なるため表示も異なる． ------------------------------------------------------------------------ >:t (a, b) (a, b) :: (F 23, F 29) -- 型が異なるため， >a + b -- 足し算できない． <interactive>:418:5: error: • Couldn't match type ‘29’ with ‘23’ Expected type: F 23 Actual type: F 29 ------------------------------------------------------------------------ >:t (a, c) (a, c) :: (F 23, F 23) -- 型が同じだから， >a + c -- 足し算できる． 5 ------------------------------------------------------------------------ >fRecip $ (11 + 28 :: F 7) Just 2 >(11 + 28) * 2 `mod` 7 1
いい感じにできた気がします．
