Re: Faster primality testing and factorization methods in Ruby

I changed the Miller-Rabin in the gist to a shorter/faster/adjustable
version which I modified a little.  Here's the new code in the gist.
------------------------------------------------------------------------

class Integer

   # Miller-Rabin prime test in Ruby
   # From: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
   # Ruby Rosetta Code:
http://rosettacode.org/wiki/Miller-Rabin_primality_test
   # I modified the Rosetta Code, as shown below

   require 'openssl'

   def primemr?(k=20) # increase k for more reliability
     n = self.abs
     return true  if n == 2 or n == 3
     return false if n % 6 != 1 && n % 6 != 5 or n == 1

     d = n - 1
     s = 0
     (d >>= 1; s += 1) while d & 1 == 0  # while d even
     k.times do
       a = 2 + rand(n-4)
       x = OpenSSL::BN::new(a.to_s).mod_exp(d,n)   #x = (a**d) % n
       next if x == 1 or x == n-1
       (s-1).times do
         x = x.mod_exp(2,n)                        #x = (x**2) % n
         return false if x == 1
         break if x == n-1
       end
       return false if x != n-1
     end
     true  # probably
   end
end

-- 
Posted via http://www.ruby-forum.com/.