Miller–Rabin primality test

F

Ftf 3k3

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
 
F

Ftf 3k3

Lars said:
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.
 
S

Srijayanth Sridhar

[Note: parts of this message were removed to make it a legal post.]

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


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

Jayanth
 
S

Srijayanth Sridhar

[Note: parts of this message were removed to make it a legal post.]

I mean when n>0

Jayanth

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


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

Jayanth
 
F

Ftf 3k3

Sandor said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top