This is preimalistyTest.txt

1) 66411949393245949268811711602826765576402057646975003006251042260813215340087318062380031915073315092183806206493533345953281647263552710655695269967337089850144857674638489475995919778552032603791816048265084649175429768094838031170157033168866305251844356097795408000548418783227194651709 2) 134369998990354300089952937559587535776969448542275036274354877139580565294709571734984987344659981049823868256870131654179172131661304459362060269620840757366012697430326153804505378003007019809128825704790720667004332036574214023754503695871165164528225447167140000490766277914641727754321849750023 3) 350536808223687511977919060832483359009317836768669652258214103827123073843034373053758260763785321365986229282203531892952280145569489750914169186355577810325921242157693434996002940313019002624407154852639600523832632005344218281955419630508564698834563246275476204963297387183644289099896194969451 4) 109222578287588161392628432977288900116322440372691822190950724986424793367338375855872480118803684491935866591900992882281792852417006406065982720056931898945846182870518134127310585251783648507814745360739122268807312467893393747083026990245098130117711479683050797261191579884907073676329793735877 5) 319705304701141539155720137200974664666792526059405792539680974929469783512821793995613718943171723765238853752439032835985158829038528214925658918372196742089464683960239919950882355844766055365179937610326127675178857306260955550407044463370239890187189750909036833976197804646589380690779463976173 

You can use this code and make the code complete

def moduloPower(a, r, p): if a == 0: return 0 elif r == 0: return 1 elif r == 1: return a % p s = moduloPower(a, r//2, p)**2 % p if r % 2 == 1: s = a*s % p return s """This is the naive implementation. It is extremely inefficient for large inputs.""" def slowModuloPower(a, r, p): return a**r % p 

2. Implement the following Primality Testing algorithm, based on Fermat's Little Theorem, efficiently. Note that k in the code is some small positive integer parameter, that you can either hardcode or pass as argument to the function. Also note that you should use the efficient implememtation of the function moduloPower from Homework 1 to compute a-1 mod n Input: a positive integer n Algorithm: FLTPRIMALITYTEST repeat k times pick an integer a at random from [1, n - 1] if an-1 mod n1, output composite and exit the program. output prime (a) Use your implementation of FLTPRIMALITYTEST algorithm to determine which of the 5 numbers in the posted text file (primalityTest.txt) are prime and which are composite (b) As you know, the FLTPRIMALITY TEST algorithm can incorrectly classify composites as primes. Set k-5 in the FLT PRIMALITY TEST algorithm and determine the number of integers in the range [500, 100000] that are, on average, incorrectly classified as primes by the algorithm. Since the algorithm is randomized, it will likely behave differently each time it is executed. So run the algorithm 10 times and report the average number of integers in the range [500, 100000] that are incorrectly classified To complete this task, your program would have to be able to correctly identify primes/composites and the easiest way to do this is to simply implement and use the naive primality testing algorithm. (c) Re-run the experiment in (b) with k 15. You should see fewer incorrect classifica- tions now (compared with k-). Once again, report the average number of integers in the range [500, 100000] that are incorrectly classified. (d) Now set k-20 and produce as output all integers in the range [500.100000] that are incorrectly classified as primes from one run of FLP PRIMALITY TEST. Compare this output with the list of Carmichael numbers less than 100000. See http://www.chalcedon.demon.co.uk/rgep/cartable.html for lists of Carmichael numbers. Are you seeing any non-Carmichael composites clas- sified as primes? 2. Implement the following Primality Testing algorithm, based on Fermat's Little Theorem, efficiently. Note that k in the code is some small positive integer parameter, that you can either hardcode or pass as argument to the function. Also note that you should use the efficient implememtation of the function moduloPower from Homework 1 to compute a-1 mod n Input: a positive integer n Algorithm: FLTPRIMALITYTEST repeat k times pick an integer a at random from [1, n - 1] if an-1 mod n1, output composite and exit the program. output prime (a) Use your implementation of FLTPRIMALITYTEST algorithm to determine which of the 5 numbers in the posted text file (primalityTest.txt) are prime and which are composite (b) As you know, the FLTPRIMALITY TEST algorithm can incorrectly classify composites as primes. Set k-5 in the FLT PRIMALITY TEST algorithm and determine the number of integers in the range [500, 100000] that are, on average, incorrectly classified as primes by the algorithm. Since the algorithm is randomized, it will likely behave differently each time it is executed. So run the algorithm 10 times and report the average number of integers in the range [500, 100000] that are incorrectly classified To complete this task, your program would have to be able to correctly identify primes/composites and the easiest way to do this is to simply implement and use the naive primality testing algorithm. (c) Re-run the experiment in (b) with k 15. You should see fewer incorrect classifica- tions now (compared with k-). Once again, report the average number of integers in the range [500, 100000] that are incorrectly classified. (d) Now set k-20 and produce as output all integers in the range [500.100000] that are incorrectly classified as primes from one run of FLP PRIMALITY TEST. Compare this output with the list of Carmichael numbers less than 100000. See http://www.chalcedon.demon.co.uk/rgep/cartable.html for lists of Carmichael numbers. Are you seeing any non-Carmichael composites clas- sified as primes