In your try_composite
function, the for
loop should be for i in range(1,s)
. Do not test the case where i
is zero.
EDIT: Also, you are missing a test in your try_composite
function. Here is my version of the pseudocode:
def isPrime(n, k=5):
def isComposite(s, d):
x = pow(randrange(2,n-1), d, n)
if x == 1 or x == n-1: return False
for r in range(1, s):
x = pow(x, 2, n)
if x == 1: return True
if x == n-1: return False
return True
if n < 2: return False
for p in [2, 3, 5, 7, 11, 13, 17]:
if n % p == 0: return n == p
s, d = 0, n-1
while d % 2 == 0: s, d = s+1, d/2
for i in range(k):
if isComposite(s, d): return False
return True
It's too bad that Python doesn't allow labels on break
or continue
statements. Here's pseudocode for a much prettier version of the function:
function isPrime(n, k=5)
if n < 2 then return False
for p in [2,3,5,7,11,13,17,19,23,29]
if n % p == 0 then return n == p
s, d = 0, n-1
while d % 2 == 0
s, d = s+1, d/2
for i from 0 to k
x = powerMod(randint(2, n-1), d, n)
if x == 1 or x == n-1 then next i
for r from 1 to s
x = (x * x) % n
if x == 1 then return False
if x == n-1 then next i
return False
return True
Notice the two places where the control flow goes to next i
. There is no good way to write that in Python. One choice uses an extra boolean variable that can be set and tested to determine when to bypass the rest of the code. The other choice, which I took above, is to write a local function to perform the task. This "loop-and-a-half" idiom is convenient and useful; it was proposed in PEP 3136 and rejected by Guido.