自分で作る Num の instance

11月14日のHIMAで、みんなが「Num の instance はよく作る」という発言をしていました。Num の instance なんて自分で作るもんじゃないと思っていた僕は衝撃を受け、どういうときに作るのが尋ねました。すると、msakai さんが「有限体での計算」と答え、「すると暗号のコードはもっと洗練できるのか？」と再び衝撃を受けました。

という訳で、昔作った RSA のコードを元に、Modulo という data を定義して Num の instance にしてみました。Haskell の累乗演算子の実装を見たところ、高速なアルゴリズムが採用されていました。それはすなわち、Haskell で RSA を作ると、これだけということです！

data Modulo = Mod Integer Integer deriving (Eq,Show)

instance Num Modulo where
    (Mod n1 m1) * (Mod n2 m2)
        | m1 == m2  = Mod (n1 * n2 `mod` m1) m1
        | otherwise = error "modulo mismatch"

fromModulo :: Modulo -> Integer
fromModulo (Mod n _) = n

rsaEncrypt :: Integer -> Integer -> Integer -> Integer
rsaEncrypt e n plain  = fromModulo $ (Mod plain n) ^ e

rsaDecrypt :: Integer -> Integer -> Integer -> Integer
rsaDecrypt d n cipher = fromModulo $ (Mod cipher n) ^ d

凄すぎて、めまいがしました。。。