Miller–Rabin primality test: Difference between revisions

Content added Content deleted
Line 1,191: Line 1,191:
| n < 100 = return (n `elem` primesTo100)
| n < 100 = return (n `elem` primesTo100)
| otherwise = do ws <- witnesses k n
| otherwise = do ws <- witnesses k n
return $ and [test n (pred n) evens d a | a <- ws]
return $ and [test n (pred n) evens (head odds) a | a <- ws]
where
where
(evens,odds) = span even (iterate (`div` 2) (pred n))
(evens,odds) = span even (iterate (`div` 2) (pred n))
d = head odds



test :: Integral nat => nat -> nat -> [nat] -> nat -> nat -> Bool
test :: Integral nat => nat -> nat -> [nat] -> nat -> nat -> Bool
Line 1,223: Line 1,221:
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y
| otherwise = f (i-1) b (b*y `rem` m)
| otherwise = f (i-1) b (b*y `rem` m)



--------------------------------------
--------------------------------------


Testing in GHCi:
Testing in GHCi:
<pre>*~> isMillerRabinPrime 4547337172376300111955330758342147474062293202868155909489
~> isPrime 4547337172376300111955330758342147474062293202868155909489
True
True


*~> isMillerRabinPrime 4547337172376300111955330758342147474062293202868155909393
*~> isPrime 4547337172376300111955330758342147474062293202868155909393
False
False


*~> dropWhile (<900) $ filter isPrime [2..1000]
*~> dropWhile (<900) $ filter isPrime [2..1000]
[907,911,919,929,937,941,947,953,967,971,977,983,991,997]</pre>
[907,911,919,929,937,941,947,953,967,971,977,983,991,997]
</lang>
</lang>


Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"