ccs130h Homework Assignment 1
ccs130h Homework Assignment 1
Implement 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.
Write your functions into a module, along with the test main program,
and a short report of your experiment and possible discoveries,
and email it to me.
This assignment is due 11pm, Sunday, November 16.
|