From: Ftf 3k3 <ftf3k3@...>
Date: 2009-06-17T20:57:12+09:00
Subject: Miller–Rabin primality test

I tried to follow the instructions here:
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
It doesn't work as expected... any help would be very appreciated.

class Integer
  def is_prime?(k)
    if self % 2 == 0
      return 'NO'
    end

    n = self
    d = n - 1
    s = 0

    while d % 2 == 0
      d /= 2
      s += 1
    end

    k.times do
      a = rand(n - 1) + 1
      t = true
      for r in 0...s
        if (a ** d) % n == 1 or (a ** ((2 ** r) * d)) % n == -1
          t = false
        end
      end
      return 'NO' if t == true
    end

    return 'YES'
  end
end

STDIN.gets.to_i.times do
  puts STDIN.gets.to_i.is_prime?(25)
end
-- 
Posted via http://www.ruby-forum.com/.