Question: implement Fermet's Little Theorem based Primality Test (question shown in the picture above)

NOTE: algorithm needs to run on the large numbers shown below for part A, I guess all other questions can be answered with a working code but I'd appreciate if you could answer all of them so I could just double check. Thanks

-------------------------------------------------

A- use your implementation to test the following 5 numbers. (note: these numbers are longer than any screen, make sure to scroll to see the full number)

66411949393245949268811711602826765576402057646975003006251042260813215340087318062380031915073315092183806206493533345953281647263552710655695269967337089850144857674638489475995919778552032603791816048265084649175429768094838031170157033168866305251844356097795408000548418783227194651709 134369998990354300089952937559587535776969448542275036274354877139580565294709571734984987344659981049823868256870131654179172131661304459362060269620840757366012697430326153804505378003007019809128825704790720667004332036574214023754503695871165164528225447167140000490766277914641727754321849750023 350536808223687511977919060832483359009317836768669652258214103827123073843034373053758260763785321365986229282203531892952280145569489750914169186355577810325921242157693434996002940313019002624407154852639600523832632005344218281955419630508564698834563246275476204963297387183644289099896194969451 109222578287588161392628432977288900116322440372691822190950724986424793367338375855872480118803684491935866591900992882281792852417006406065982720056931898945846182870518134127310585251783648507814745360739122268807312467893393747083026990245098130117711479683050797261191579884907073676329793735877 319705304701141539155720137200974664666792526059405792539680974929469783512821793995613718943171723765238853752439032835985158829038528214925658918372196742089464683960239919950882355844766055365179937610326127675178857306260955550407044463370239890187189750909036833976197804646589380690779463976173 

------------------------------------------------

B- FLTPrimalityTest 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 classifications now (compared with k = 5). 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 classified as primes?

Please write the algorithm in Java

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, 1 if an-1 mod n 1, output composite and exit the program output prime 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, 1 if an-1 mod n 1, output composite and exit the program output prime