In preparation for some upcoming project euler problems I’ve been looking for faster methods of determining if a number is prime. One such method I’ve come across was the Miller-Rabin primality test which is a probabilistic test for determining if a given number is probably prime. The higher the value of s passed to the original function the higher the probability the answer is correct.

I found an example of this algorithm in python which I’ve rewritten to use in F#, I do not have the original python source but if you are interested in learning more you can check out the Wikipedia page.

The following code snippet uses .net 4′s BigInteger class for part of test. I have plans to rewrite it making more f# like right now its a direct translation of the python code.

open System.Numerics

let rec toBinary (n:BigInteger) r =
    if n > BigInteger.Zero then
        toBinary (n/(BigInteger 2)) (r @ [n% (BigInteger 2)])
    else
        r

let test (a:BigInteger) (n:BigInteger) =
    let (b:List<BigInteger>) = toBinary (n - BigInteger.One) []
    let mutable d = BigInteger.One
    let mutable Prime = false
    let CheckList = [0 .. b.Length-1 ] |> List.rev
    for i in CheckList do
        let x = d
        d <- (d*d) % n
        if (d = BigInteger.One && x <> BigInteger.One && x <> n-BigInteger.One) then
            Prime <- true // complex
        if b.[i] = BigInteger.One then
            d <- (d*a) % n
    if d <> BigInteger.One then
        Prime <- true //complex
    Prime //if its still false then prime

let Rand = new System.Random()

let MillerRabin (n:uint64) (s:int) =
    let mutable Prime = true
    for j in [1 .. s+1] do
        let a = Rand.Next(1, Convert.ToInt32(n)-1)
        if (test (BigInteger a) (BigInteger n)) then
            Prime <- false
    Prime