Quantum Homework 4 Solved

Description

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.

• q = 10601
• q = 101101
• q = 15841

2. (i) Compute 7⁷ in Z4.

77

• Compute 7 in Z4.
• Compute 7⁷⁷⁷ in Z5 [Hint 1: use the previous part and Fermat’s little theorem.] [Hint 2: 7³.]

3. Compute 2³⁴⁵ 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).
   • Prove that if gcd(m,n) = 1 then ϕ(m n) = ϕ(m)ϕ(n).
   • Prove that if p is a prime then

.

• Use the previous parts to prove that

(the product is over all prime divisors of n).