Rosetta Code

Miller–Rabin primality test: Difference between revisions

Page Discussion

Miller–Rabin primality test (view source)

Revision as of 22:27, 11 October 2009

56 bytes removed ,  14 years ago
→‎{{header|Haskell}}
Line 495:
fs = [[31,73],[2,7,61],[2,3,5,7,11],[2,3,5,7,11,13],[2,3,5,7,11,13,17]]
if y >= 341550071728321
then return ($ take x $ randomRs (2,y-1) g)
else return ($ (fs!!).head.concat $ zipWithfindIndices (\i v -> [i | v > y]) [0..]$ r)
 
isMillerRabinPrime :: Integer -> IO Bool
Line 503:
else do
let pn = pred n
e = until (odd . last) (ap (++) `ap` (return. flip (`div` 2). last)) [pn];
try [] = return True. all (\a -> let c = map (powerMod n a) e in
try (a:as) = if any (==pn) c || (1 == last c) then try as else return False pn `elem` c || last c == 1)
where c = map (powerMod n a) e
witns 100 n >>= try</lang>
Testing in GHCi:
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/107735"