sawine@2: isProbPrime = True
sawine@2: 
sawine@2: import sys
sawine@2: from math import log
sawine@2: from random import randint
sawine@2: 
sawine@2: def main():
sawine@2: 	args = parse_args()
sawine@2: 	n = args.n
sawine@2: 	if args.s:
sawine@2: 		if safe_is_prime(n):
sawine@2: 			print "%i is most probably a prime number." % n
sawine@2: 		else:
sawine@2: 			print "%i is not a prime number." % n
sawine@2: 		return 
sawine@2: 	elif args.a:
sawine@2: 		a = args.a
sawine@2: 	else:
sawine@2: 		a = randint(2, n-1)
sawine@2: 	if is_prime(n, a):
sawine@2: 		print "%i is probably a prime." % n	
sawine@2: 	else:
sawine@2: 		print "%i is not a prime." % n
sawine@2: 
sawine@2: def safe_is_prime(n):
sawine@2: 	aset = set()
sawine@2: 	while len(aset) < int(log(n)):
sawine@2: 		aset.add(randint(2, n-1))
sawine@2: 	for a in aset:
sawine@2: 		if not is_prime(n, a):
sawine@2: 			return False
sawine@2: 	return True
sawine@2: 	
sawine@2: def is_prime(n, a=None):
sawine@2: 	if not a:
sawine@2: 		a = randint(2, n-1)
sawine@2: 	global isProbPrime
sawine@2: 	isProbPrime = True
sawine@2: 	#print "Prime Test for %i with a = %i:" % (n, a)
sawine@2: 	r = power(a, n-1, n)
sawine@2: 	if r != 1 or not isProbPrime:
sawine@2: 		#print "=> %i is not a prime." % n
sawine@2: 		return False
sawine@2: 	else:
sawine@2: 		#print "=> %i is probably a prime." % n
sawine@2: 		return True
sawine@2: 
sawine@2: def power(a, p, n):
sawine@2: 	global isProbPrime	
sawine@2: 	if p == 0:
sawine@2: 		return 1
sawine@2: 	x = power(a, p/2, n)
sawine@2: 	r = (x*x)%n
sawine@2: 	#print "power(%i, %i, %i)" % (a, p, n)
sawine@2: 	#print "result = %i" % r
sawine@2: 	if r == 1 and x != 1 and x != n-1:
sawine@2: 		isProbPrime = False
sawine@2: 		#print "isProbPrime = False"
sawine@2: 	if p%2 == 1:
sawine@2: 		r = (a*r)%n
sawine@2: 		#print "updated result = %i" % r
sawine@2: 	return r
sawine@2: 
sawine@2: from argparse import ArgumentParser
sawine@2: 
sawine@2: def parse_args():
sawine@2:     parser = ArgumentParser(description='Applies the randomised prime number test.')
sawine@2:     parser.add_argument('n', type=int, help='number to be tested')
sawine@2:     parser.add_argument('-a', type=int, help='provide a yourself')
sawine@2:     parser.add_argument('-s', action='store_true', help='multiple tests to minimise probability of failure')
sawine@2:     return parser.parse_args()
sawine@2: 
sawine@2: if __name__ == "__main__":
sawine@2:     main()