SICP : Ex1.28

これは、素数判定を確率的なテストを用いて行うという問題。fermat-testというテストが本編で解説されていて、問題では、miller-rabin-testというテストを使って書き直すことが求められた。
この問題もConcurrent Cleanを使って回答します。
id:lethevert:20060108:p1 で定義した乱数ライブラリと、次のような関数をライブラリとして使用します。（これらは、今後の問題で、継続して使っていきます）

($) infixl 0 //:: (a -> b) a -> b
($) f a :== f a

//累乗の剰余
expmod :: !Int !Int !Int -> Int
expmod _ 0 _ = 1
expmod base exp m
	| exp < 0
		= abort "^ (Int) called with negative power argument"
		= expmod exp
where
	expmod :: !Int -> Int
	expmod 0 = 1
	expmod exp
		| isEven exp
			= (rem) $ (expmod $ exp/2)^2
					$ m
		| otherwise
			= (rem) $ base * (expmod $ exp-1)
					$ m

回答

コメントアウトした方がfermat-testです。

fast_prime_p :: Int Int -> Bool
fast_prime_p n times
	= fst $ fast_prime_p` times mkRandomInt
where
	fast_prime_p` 0 r = (True, r)
	fast_prime_p` times r
		# (ok, r) = miller_rabin_test n r //fermat_test n r
		| ok
			= fast_prime_p` (times-1) r
		| otherwise
			= (False, r)


fermat_test :: Int *(Random Int) -> (Bool, *(Random Int))
fermat_test n r
	# (i, r) = nextRand r
	= (try_it $ 1 + i rem (n-1), r)
where
	try_it a = a == expmod a n n


miller_rabin_test :: Int *(Random Int) -> (Bool, *(Random Int))
miller_rabin_test n r
	# (i, r) = nextRand r
	= (try_it $ 1 + i rem (n-1), r)
where
	try_it a = 1 == expmod a (n-1) n