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

Okay, I’m writing this because a lot of people in my math class are having problems with this and because I still have (some) faith in humanity I’ll assume there difficulty is due to a lack of sources from which to learn. So today’s topic is “Inverse Functions”…
So to start a inverse function “inverts” the input/output of a function. For instance if a function does this:
[math]f(x) doubleright b[/math]
Then the inverse would do this:
[math]{f^{-1}}(b) doubleright x[/math]
So basically the input into the first function is the output of the second function. Also note that the inverse function (the second one) has a [math]{f^{-1}}(x)[/math] instead of [math]f(x)[/math] This is how you donate that the function is the inverse. That said, lets look at some examples. The most basic of which would look like so.
[math]f(x) = x^2[/math]
[math]{f^{-1}}(x)= sqrt{x}[/math]
That should be very easy to follow. basically the first function takes a number and squares it the second takes the squared number and turns it into the starting number. In order to find the inverse of a function one needs to simply swap the “f(x)” and the “x” and solve for “x” again. Here’s a quick example starting and the first function and following all of the steps to get to the inverse.

[math]f(x)={(x-2)^2}/{21}[/math]
[math]x={(f(x)-2)^2}/{21}[/math]
[math]21x={(f(x)-2)^2}[/math]
[math]sqrt{21x}=f(x)-2[/math]
[math]{f^{-1}}(x)=(sqrt{21x})+2[/math]

So then, using 5 as our “x” value the starting function gives us .4285714286 putting that answer into the inverse function gives us 5. So the inverse simply takes the output of the first function and tells you that the input into the first function was (please note that the provided example only works with positive numbers). Hopefully this will help anyone confused by this subject.