gistfile1.rb

def mr(n)
  # n = (2**k)*m + 1 | m is odd
  m = 0
  k = 0
  until m.odd? do
    k += 1
    m = (n - 1)/(2**k)
  end
  
  a = rand(n-2)+1
  b = (a**m)%n
   
  return "prime" if b==1

  0.upto(k-1).each do |ki|
    if b == -1%n
      return "prime"
    else
      b = (b**2)%n
    end
  end
  return "composite"
end

puts "#{589081} is #{mr(549081)}"