check_prime.rb

require "benchmark"
require "prime"

class Integer
  # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
  def prime?
    n = self.abs()
    return true if n == 2
    return false if n == 1 || n & 1 == 0

    # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
    # http://everything2.com/index.pl?node_id=1176369

    return false if n > 3 && n % 6 != 1 && n % 6 != 5     # added

    d = n-1
    d >>= 1 while d & 1 == 0
    20.times do                               # 20 = k from above
      a = rand(n-2) + 1
      t = d
      y = ModMath.pow(a,t,n)                  # implemented below
      while t != n-1 && y != 1 && y != n-1
        y = (y * y) % n
        t <<= 1
      end
      return false if y != n-1 && t & 1 == 0
    end
    return true
  end
end

module ModMath
   def ModMath.pow(base, power, mod)
     result = 1
     while power > 0
       result = (result * base) % mod if power & 1 == 1
       base = (base * base) % mod
       power >>= 1;
     end
     result
   end
end

n = 4

Benchmark.bm(7) do |x|
  x.report("For milner") { n.times { 
      107565456790871.prime? 
    }
  }
  x.report("For prime class") { n.times { 
      Prime.prime?(107565456790871)
    }
  }
end

             user     system      total        real
For milner  0.000000   0.000000   0.000000 (  0.002970)
For prime class 10.520000   0.370000  10.890000 ( 11.033578)