1. If a number n is composite but in the Miller-Rabin algorithm Test (n,a) outputs "n is probably prime" (see the textbook page 178https://calclab.math.tamu.edu/~rahe/2014a_673_700720/Trappe_2006.pdf), then a is said to be a false Miller-Rabin witness for n. Show that 2 is a false Miller-Rabin witness strong for 2047.
2. Let p = 101 (note that 101 is a prime number). It is known that 2 is a primitive root of 101. For any number n in the range {1,2,..., 100}, we denote by L2(n) the value k ∈ {1,2,..., 100} such that 2k = n (mod 101) (i.e., L2(n) is the discrete log of n mod 101).
a) What is L2(1)? Justify your answer. (Note: The answer k= 0 is not valid, because k has to be in the set {1,2,..., 100} ).
(b) Using the fact that L2(3) = 69, determine L2(9). Justify your answer.
3. It can be shown that 5 is a primitive root for the prime 1223. You want to solve the discrete logarithm problem 5^x = 3 (mod 1223).
Given that 3^611 = 1 (mod 1223), determine whether x is even or odd. Follow the below step for correct answers
Hints: First see how much is 5611 x (mod 1223) using the information given in the problem. Then use the fact that the equation y2 = 1 (mod 1223) has the solutions 1 and -1. Next let y = 5611 (mod 1223). How much is y2 (mod 1223) (recall that 1223 is prime) ? How much is y?