[Solved] Quantum Homework 4

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 Fermats 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).