I can't guarantee the correctness of the implementation, but a friend (burke on HN, I believe) and I wrote a version of the Miller-Rabin primality test in Ruby

I can't guarantee the correctness of the implementation, but a friend (burke on HN, I believe) and I wrote a version of the Miller-Rabin primality test in Ruby & C that you may want to use as reference. IIRC numbers under 341,550,071,728,321 could be accurately tested for primality on the "instant" timescale. See the repo on github: https://github.com/rkneufeld/mr_prime/blob/master/lib/mr_prime/mr_prime_rb.rb https://github.com/rkneufeld/mr_prime/blob/master/lib/mr_pri...