This example provides an implementation of the Miller-Rabin primality test
[1] in Haskell. Note that, this is not a deterministic test. The test is
checking the primality using 20 random witnesses. This list can be changed in
the function isprime
. A longer witnesses list will produce a more accurate
but slower test.
This is a pet project to get myself bootstrapped into Haskell :)
[1] Wikipedia
- Primes.hs
- isprime.hs
- LICENSE
- README.md
Primes.hs
is the main module exporting three functions:
-
isPrime seed num
it tests the primality of num
-
nextPrime seed num
it returns the next prime number greater or equal to num
-
randomPrime seed nbits
it returns a random prime number of nbits
isprime.hs
is a haskell program example using the Primes module.
You can compile it as follows:
> ghc -o isprime isprime.hs
And use it
> ./isprime 111
False
> ./isprime 101
True
Cheking the primality of a 4096 bits prime number takes less than 1.5 secs on my laptop
time ./isprime
63403550607883752100349311689727327703738578425673901007749857445440140528085542
07855079268451299922883210761569405604371997181210940291172703418229373367232947
27596840346335806913455472480308846898965516642225470546475140136215945842100163
68546937832595450710522089161886334713799157046889240432457897282783812290841771
27478864057932440461510830491998385781411523299574670880890696269333893691647904
61247144627090876086303349677138799441212072733008335832801976019271795698218922
85292546110307251539619562052593831024192566983075713832773374919731256635028366
94847657715925805965250536202523329860263356023223562978732719919382845575729929
27676206624507373569213706534721538860824540533866568911694439872023964053725799
02395209390512791178752105617303869321944544063071774967202072276744089746550212
18948540193104749075842021301907318827591632795117297393770096393304807267539018
26124075710332661221836777960500764309777751327826972545334676599645448580840839
10626603807006204470707551826831618464304605990319191825603475419787227690223908
97934262452564556131020964732707475075962817682168116114272026797111925860822664
62361617225019754646844194598598203064373636566222033813355791022493894193943319
284428210604180762180486537914317
True
real 0m1.479s
user 0m1.350s
sys 0m0.021s