What's the problem of my prime test code?

I implemented the Miller-Rabin prime test algorithm found on wikipedia with Python 3.

It seems to be working correctly with most numbers but occasionaly fail on certain numbers.

For example, the prime number 99999999999999997 is judged to be NOT prime.

I implemented the algorithm line by line and I have no clue where the problem is. Can any one help me ?

Here is my code.

the test input is:

1

99999999999999997

(No empty line between two lines.)

And the expected output should be YES, but it gives NO on my machine.

import random

def isPrime(n, k = 5):
'''
Primality test using Miller-Rabin method.
n The number to test primality.
k The number of M-R test to perform.
'''
if n == 1:
    return False
if n == 2 or n == 3:
    return True
if n % 2 == 0:
    r开发者_StackOverflow中文版eturn False

# Calculate d
nn = n - 1
s = 1
while nn % (2 ** s) == 0:
    s += 1
s -= 1
d = int(nn / (2 ** s))

for i in range(k):
    a = random.randint(2, n - 1)
    x = pow(a,d,n)
    if x == 1 or x == n - 1:
        continue
    flag = True
    for r in range(1, s):
        x = pow(x,2,n)
        if x == 1:
            return False
        if x == n - 1:
            flag = False
            break
    if not flag:
        continue
    return False
return True

count = int(input())
for i in range(count):
    if isPrime(int(input())):
        print('YES')
    else:
        print('NO')

This is an implementation of Miller-Rabin I wrote a while ago. It has never given me an unexpected result -- though that doesn't mean it won't! It is substantially identical to the one you pasted, and it declares 99999999999999997 to be prime. Yours did too, when I tested it -- so that's a second to Mikola's opinion. But see below for one possible problem that I can't easily test... scratch that, I tested it, and it was the problem.

When it comes to primality testing, I'm no expert, but I spent a lot of time thinking about and coming to understand Miller-Rabin, and I'm pretty sure your implementation is spot-on.

def is_prime_candidate(self, p, iterations=7):  
    if p == 1 or p % 2 == 0: return False       
    elif p < 1: raise ValueError("is_prime_candidate: n must be a positive integer")
    elif p < self.maxsmallprime: return p in self.smallprimes

    odd = p - 1
    count = 0
    while odd % 2 == 0:
        odd //= 2
        count += 1

    for i in range(iterations):
        r = random.randrange(2, p - 2) 
        test = pow(r, odd, p)
        if test == 1 or test == p - 1: continue
        for j in range(count - 1):
            test = pow(test, 2, p)
            if test == 1: return False
            if test == p - 1: break
        else: return False
        print i
    return True

The one thing I noticed about your code that seemed off was this:

d = int(nn / (2 ** s))

Why int, I thought to myself. Then I realized you must be using Python 3. So that means you're doing floating point arithmetic here and then converting to int. That seemed iffy. So I tested it on ideone. And lo! the result was False. So I changed the code to use explicit floor division (d = nn // (2 ** s)). And lo! it was True.

I am going to reiterate my comment, since my testing seems to indicate your example is working. I strongly suspect that you just mistyped your test case. Maybe you can try taking a second look at it? Here is what I got from running it:

In [12]: millerrabin.isPrime(99999999999999997, 5)

Out[12]: True

EDIT: I just ran the updated version, and here is the output from the console:

1
99999999999999997
YES

Again, this looks correct.

From what I can see, the Miller-Rabin algorithm is only probabilistic. Were you not aware of this, or are you using a modified, non probabilistic version?