# Miller–Rabin primality test

**URL:** <https://www.ruby-forum.com/t/millera-rabin-primality-test/170421>\
**Category:** Ruby\
**Created:** [June 17, 2009, 1:57pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421 "2009-06-17T13:57:07Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 1:57pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/1 "2009-06-17T13:57:07Z")

</div>

I tried to follow the instructions here:

> **[Rabin-Miller Strong Pseudoprime Test -- from Wolfram MathWorld](https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html)**
>
> A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime. It is based on the properties of strong pseudoprimes. The algorithm proceeds as follows. Given an odd integer n, let n=2^rs+1 with s odd....

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

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 2:15pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/2 "2009-06-17T14:15:25Z")

</div>

On Wed, Jun 17, 2009 at 1:57 PM, Ftf 3k3 [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> I tried to follow the instructions here:  
> [Rabin-Miller Strong Pseudoprime Test -- from Wolfram MathWorld](http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html)  
> 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)) ?

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 2:58pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/3 "2009-06-17T14:58:16Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 3:03pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/4 "2009-06-17T15:03:33Z")

</div>

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

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

Jayanth

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 6:47pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/5 "2009-06-17T18:47:41Z")

</div>

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](http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html)  
> ---------------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

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 3:04pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/6 "2009-06-17T15:04:08Z")

</div>

I mean when n\>0

Jayanth

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 17, 2009, 7:24pm UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/7 "2009-06-17T19:24:24Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ftf3k3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/f/b9bd4f/32.png) [@ftf3k3](https://www.ruby-forum.com/u/ftf3k3)\
**Post date:** [June 18, 2009, 8:45am UTC](https://www.ruby-forum.com/t/millera-rabin-primality-test/170421/8 "2009-06-18T08:45:45Z")

</div>

On Jun 17, 1:24 pm, Ftf 3k3 [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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](http://snippets.dzone.com/posts/show/4636)