Mercurialalgorithms_theory / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
examples/prime.py
author lindenmannm
Tue, 08 Mar 2011 21:11:05 +0100
changeset 12 8e872e077a21
permissions -rw-r--r--
fs ml 
     1 isProbPrime = True

     2 

     3 import sys

     4 from math import log

     5 from random import randint

     6 

     7 def main():

     8 	args = parse_args()

     9 	n = args.n

    10 	if args.s:

    11 		if safe_is_prime(n):

    12 			print "%i is most probably a prime number." % n

    13 		else:

    14 			print "%i is not a prime number." % n

    15 		return 

    16 	elif args.a:

    17 		a = args.a

    18 	else:

    19 		a = randint(2, n-1)

    20 	if is_prime(n, a):

    21 		print "%i is probably a prime." % n	

    22 	else:

    23 		print "%i is not a prime." % n

    24 

    25 def safe_is_prime(n):

    26 	aset = set()

    27 	while len(aset) < int(log(n)):

    28 		aset.add(randint(2, n-1))

    29 	for a in aset:

    30 		if not is_prime(n, a):

    31 			return False

    32 	return True

    33 	

    34 def is_prime(n, a=None):

    35 	if not a:

    36 		a = randint(2, n-1)

    37 	global isProbPrime

    38 	isProbPrime = True

    39 	#print "Prime Test for %i with a = %i:" % (n, a)

    40 	r = power(a, n-1, n)

    41 	if r != 1 or not isProbPrime:

    42 		#print "=> %i is not a prime." % n

    43 		return False

    44 	else:

    45 		#print "=> %i is probably a prime." % n

    46 		return True

    47 

    48 def power(a, p, n):

    49 	global isProbPrime	

    50 	if p == 0:

    51 		return 1

    52 	x = power(a, p/2, n)

    53 	r = (x*x)%n

    54 	#print "power(%i, %i, %i)" % (a, p, n)

    55 	#print "result = %i" % r

    56 	if r == 1 and x != 1 and x != n-1:

    57 		isProbPrime = False

    58 		#print "isProbPrime = False"

    59 	if p%2 == 1:

    60 		r = (a*r)%n

    61 		#print "updated result = %i" % r

    62 	return r

    63 

    64 from argparse import ArgumentParser

    65 

    66 def parse_args():

    67     parser = ArgumentParser(description='Applies the randomised prime number test.')

    68     parser.add_argument('n', type=int, help='number to be tested')

    69     parser.add_argument('-a', type=int, help='provide a yourself')

    70     parser.add_argument('-s', action='store_true', help='multiple tests to minimise probability of failure')

    71     return parser.parse_args()

    72 

    73 if __name__ == "__main__":

    74     main()
algorithms_theory