QUANTUM ALGORITHMS
1. For each of the following values of q, generate 5 random members of {1,...,q − 1} and run the Miller-Rabin test using them. What is the probability that q is prime?
You should run the algorithm by hand, but I suggest using a computer to do the calculations themselves.
(i) q = 10601
(ii) q = 101101
(iii) q = 15841
2. (i) Compute 77 in Z4.
77
(ii) Compute 7 in Z4.
(iii) Compute 7777 in Z5 [Hint 1: use the previous part and Fermat’s little theorem.] [Hint 2: 73.]
3. Compute 2345 mod 79. I suggest that you do this without using a computer. [Hint: 78 = 2 · 3 · 13.]
4. Let n ∈ N and define (i.e. the number of numbers coprime to n between 1 and n).
(i) Prove that if gcd(m,n) = 1 then ϕ(m · n) = ϕ(m)ϕ(n).
(ii) Prove that if p is a prime then
.
(iii) Use the previous parts to prove that
(the product is over all prime divisors of n).
