Paper , Order, or Assignment Requirements

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 178 http://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 L₂(n) the value k Î {1,2,…, 100} such that 2^k = n (mod 101)  (i.e., L₂(n) is the discrete log of n  mod 101).
   1. What is L₂(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 L₂(3) = 69, determine L₂(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 5^{611 x} (mod 1223) using the information given in the problem.  Then use the fact that the equation y² = 1 (mod 1223) has the  solutions 1 and -1.  Next let y = 5⁶¹¹ (mod 1223). How much is y² (mod 1223) (recall that 1223 is prime) ? How much is y?