## ccs130h Homework Assignment 1Implement the Fermat and the Miller-Rabin primality testing algorithms using Python 3. If you don't have Python on your computer, you may download Python 3.4.2 from python.org. This will allow to also install IDLE which is an interactive environment for writing and executing Python programs and functions, and importing popular modules such as math, turtle, and random.The input, output interfaces of the Fermat and Miller-Rabin functions can be as follows, however, you are free to make your own design choices. - The function fermat(n, k) receives the integer n to be tested,
and runs the Fermat's test k times for randomly or not-so-randomly
chosen k bases. If the function finds a witness, it returns False
(implying n is not prime) and value of the witness w. If no witness
is found for k distinct bases, it should return True (implying n is
probably prime)
- The function mr(n, k) receives the integer n to be tested,
and runs the Miller-Rabin test k times for randomly or not-so-randomly
chosen k bases. If the function finds a witness, it returns False
(implying n is not prime) and value of the witness w. If no witness
is found for k distinct bases, it should return True (implying n is
probably prime)
- Experiment with your functions using Carmichael numbers and calculate the exact success probabilities of Fermat and Miller-Rabin tests.
This assignment is due 11pm, Sunday, November 16. |