Description

HOMEWORK 3 ADDITIONAL PROBLEMS
PROF. MATTHEW MOORE
1. Implement the Miller-Rabin probabilistic primality testing algorithm as presented in class (or in the textbook). Fill in the function is_prime_MR(q) in the python source file. You need only submit your function with the homework, not the entire source file.
2. Find five pairs of numbers q ∈ Z and a ∈ {1,…,q − 1} such that q is composite but passes the Miller-Rabin test with the given choice of a.
1