#Question 1 - Primes
# Write a function to determine whether a given number is prime or not (divisible only by itself and 1). Use the Wikipedia definition of a prime number (https://en.wikipedia.org/wiki/Prime_number) as a reference.
#
def witness_loop_xl(n, k, r, d):
# WitnessLoop: repeat k times:
while k > 0:
# pick a random integer a in the range [2, n - 2]
a = random.randint(2, n - 2)
# x <- a^d mod n
x = pow(a, d, n)
# if x = 1 or x = n - 1 then do next WitnessLoop
if x != 1 and x != n - 1:
do_next = False
# repeat r - 1 times:
for i in xrange(1, r):
# x <- x^2 mod n
x = pow(x, 2, n)
# if x = 1 then return composite
if x == 1:
return False
# if x = n - 1 then do next WitnessLoop
elif x == n - 1:
do_next = True
break
# return composite
if not do_next:
return False
k -= 1
# return probably prime
return True
def witness_loop(n, k, r, d):
# WitnessLoop: repeat k times:
# pick a random integer a in the range [2, n - 2]
for a in random.sample(xrange(2, n - 1), min(k, n - 3)):
# x <- a^d mod n
x = pow(a, d, n)
# if x = 1 or x = n - 1 then do next WitnessLoop
if x != 1 and x != n - 1:
do_next = False
# repeat r - 1 times:
for i in xrange(1, r):
# x <- x^2 mod n
x = pow(x, 2, n)
# if x = 1 then return composite
if x == 1:
return False
# if x = n - 1 then do next WitnessLoop
elif x == n - 1:
do_next = True
break
# return composite
if not do_next:
return False
# return probably prime
return True
###
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
#
def miller_rabin(n, k):
# Input: n > 3, an odd integer to be tested for primality;
# Input: k, a parameter that determines the accuracy of the test
# Output: composite if n is composite, otherwise probably prime
if n <= 1:
return False
elif n <= 3:
return True
elif n & 1 == 0:
return False
elif k < 1:
# raise ValueError('need to repeat at least one time.')
k = 1
# realign for excess test runs.
k = min(k, n - 3)
# write n - 1 as 2^r*d with d odd by factoring powers of 2 from n - 1
r = 0
d = n - 1
while d & 1 == 0:
r += 1
d >>= 1
if k < sys.maxint / 2:
# random.sample cause memory error with large test samples.
return witness_loop(n, k, r, d)
else:
# with large random sample set,
# avoiding possible non-distinct test samples,
# can be sacrificed for memory conservation with minimum risk.
return witness_loop_xl(n, k, r, d)
def question1():
# use cases.
test = [[5, sys.maxint], [2047, 1], [25326001, 1], [sys.maxint, 7], [997, 2]]
for n, k in test:
print 'test number %d (%d times): %r.' % (n, k, miller_rabin(n, k))
# edge cases.
test = [[0, 0], [0, sys.maxint], [0, -sys.maxint - 1],
[-sys.maxint - 1, 0], [-sys.maxint - 1, sys.maxint], [-sys.maxint - 1, -sys.maxint - 1],
[sys.maxint, 0], [sys.maxint, -sys.maxint - 1], [sys.maxint, sys.maxint]]
for n, k in test:
print 'test number %d (%d times): %r.' % (n, k, miller_rabin(n, k))
if __name__ == "__main__":
question1()
留言列表
