millerrobin.rb

def zeuge(a, n)
  b = (n-1).to_s(2) # binary representation
  d = 1
  
  b.reverse.split('').each do |i| 
    d = (d*d) % n
    if i.to_i == 1
      d = (d*a) % n
    end
    puts "#{i}: #{d}"
  end

  if d != 1
    puts true
  else
    puts false
  end
end

zeuge(ARGV[0].to_i, ARGV[1].to_i)


# Output
# ruby millerrobin.rb 11 161
# 7: 1
# 6: 1
# 5: 1
# 4: 1
# 3: 1
# 2: 11
# 1: 121
# 0: 51
# true => n is not a prim number