@seadog007
import System.Random
import Data.Maybe
millerTest :: Int -> Int -> Int -> Bool
millerTest d n rnd = (n2f (third (until test loop (x0,d0,s0)))) where
n2f (Just x) = x
n2f Nothing = False
a = rnd
third (_,_,x) = x
x0 = (a^d) `mod` n
d0 = d
s0 = Nothing
loop (x,d,s) = (x',d',s') where
x' = (x*x) `mod` n
d' = d*2
s' =
if (x==1)
then Just False
else if (x == n-1)
then Just True
else Nothing
test (x,d,s) = (d==n-1) || isJust s
isPrime :: StdGen -> Int -> Int -> Bool
isPrime rng k n
| n<=1 || n== 4 = False
| n<=3 = True
| otherwise = all (millerTest d n) rnds where
rnds = randomRs (2,n-2) rng
loop x = x `div` 2
cond x = ((x `mod` 2) /= 0)
d = until cond loop (n-1)