いまさらながら，素数判定 @ Haskell

とりあえず，試し割りとMiller-Rabin．

Miller-Rabinはアルゴリズム自体は簡単．

なんで，こんなコードがほぼ正しい答えを返すか若干不思議である

（乱択アルゴリズムは，相当単純なのに，まぁまぁなものが多い）．

決定性アルゴリズムも実装したいが…

module IsPrime where
import Control.Arrow (first)
import Modulo (powMod)
-- ============================================================
-- Primality test by trial division
-- ============================================================
primes :: Integral a => [a]
primes = 2:filter isPrimeDivision [3,5..]
isPrimeDivision :: Integral a => a -> Bool
isPrimeDivision 1 = False
isPrimeDivision n = all ((/=).mod n).takeWhile (<=u) $ primes
where u = floor.sqrt.fromIntegral $ n
-- ============================================================
-- Primality test by Miller-Rabin
-- ============================================================
-- if a = 2^r * d then return (r, d)
index2 :: (Integral a, Enum b, Num b) => a -> (b, a)
index2 a | even a    = first succ.index2.div a $ 2
| otherwise = (, a)
-- True  : n is probably prime
-- False : n is composite
millerRabinPrimality :: (Integral a, Integral b) => a -> Int -> b -> a -> Bool
millerRabinPrimality n s d a
| powMod a d n == 1 = True
| otherwise         = any (== n - 1).take s.iterate ((`mod` n).(^2)).powMod a d $ n
isPrimeMillerRabin :: (Integral a) => a -> Int -> Bool
isPrimeMillerRabin n k
| n == 1    = False
| n == 2    = True
| even n    = False
| otherwise = all (millerRabinPrimality n s d).take k.takeWhile (< n) $ primes
where (s,d) = index2 $ n - 1

コードをよーく見ると分かるが，このMiller-Rabin乱択アルゴリズムになっていないというオチ．

ランダムに選んでチェックではなく，素数を前から順に何個かチェックになっている．