Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|Haskell}}
Line 1,183:
-- Miller-Rabin wrapped up as an (almost deterministic) pure function
isPrime :: Integer -> Bool
isPrime n = unsafePerformIO (isMillerRabinPrime 100 n)
isMillerRabinPrime :: Integer -> IO Bool▼
isMillerRabinPrime
| even n = return (n==2)
| n < 100 = return (n `elem` primesTo100)
| otherwise = do ws <- witnesses
return $ and
where
test :: Integral nat => nat -> nat -> [nat] -> nat -> nat -> Bool
test n n_1
where
x = powerMod n a d
▲ (evens,odds) = span even (iterate (`div` 2) n_1)
powers = map (powerMod n
witnesses :: (Num a, Ord a, Random a) => Int -> a -> IO [a]
Line 1,209 ⟶ 1,214:
primesTo100 :: [Integer]
primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
-- powerMod m x n = x^n `mod` m
Line 1,218 ⟶ 1,224:
| otherwise = f (i-1) b (b*y `rem` m)
--------------------------------------
Testing in GHCi:
Line 1,228 ⟶ 1,235:
*~> dropWhile (<900) $ filter isPrime [2..1000]
[907,911,919,929,937,941,947,953,967,971,977,983,991,997]</pre>
▲ d := n-1
=={{header|J}}==
|