Miller–Rabin primality test

Ruby
1

I tried to follow the instructions here:

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

2

On Wed, Jun 17, 2009 at 1:57 PM, Ftf 3k3 [email protected] wrote:

I tried to follow the instructions here:
Rabin-Miller Strong Pseudoprime Test -- from Wolfram MathWorld
It doesn’t work as expected… any help would be very appreciated.

You don’t say what you expected and how it actually works.

Hint: How big a number is (a ** ((2 ** r) * d)) ?

3

Lars C. wrote:

You don’t say what you expected and how it actually works.

Hint: How big a number is (a ** ((2 ** r) * d)) ?

I expect it to return ‘YES’ if the number is prime and otherwise ‘NO’.
Unfortunately, it returns ‘NO’ all the time.

4

(a ** ((2 ** r) * d)) % n == -1

Can that be true? Can a remainder ever be negative?

Jayanth

5

On 17.06.2009, at 13:57, Ftf 3k3 wrote:

I tried to follow the instructions here:
Rabin-Miller Strong Pseudoprime Test -- from Wolfram MathWorld
---------------8<-------------
if (a ** d) % n == 1 or (a ** ((2 ** r) * d)) % n == -1

According to the page you posted your condition is not correct.
I don’t read it carefully nor I tested it but it’s obvious that
you forget to calculate the -1 mod n
… == (-1 % n)

Hth. regards, Sandor
Szücs

6

I mean when n>0

Jayanth

7

Sandor Szücs wrote:

According to the page you posted your condition is not correct.
I don’t read it carefully nor I tested it but it’s obvious that
you forget to calculate the -1 mod n

Thanks it seems to be working now, sometimes you just miss the obvious.

8

On Jun 17, 1:24 pm, Ftf 3k3 [email protected] wrote:

Sandor Szücs wrote:

According to the page you posted your condition is not correct.
I don’t read it carefully nor I tested it but it’s obvious that
you forget to calculate the -1 mod n

Thanks it seems to be working now, sometimes you just miss the obvious.

Posted viahttp://www.ruby-forum.com/.

Also see Ruby code here:

http://snippets.dzone.com/posts/show/4636