CS-235. Problem Set 10

1. Prove the following statements directly (from definitions, without using any Theorems), for a prime p and group Zp* :

a) Exponents work mod p-1:  if x = y (mod p-1) then for any a, ax = ay (mod p).

b) If g is a generator, then  gx = 1 iff (p-1)|x.
c) If a is a generator, then the converse of a) also holds: for any generator g and any x,y, if gx = gy (mod p), then x = y (mod p-1).

2. Let q1,q2,p1,p2 be distinct primes such that  p1=2q1+1 and p2=2q2+1 and n=p1 p2. Using CRT, show that QRn is cyclic.
(Hint: Try to construct a generator. What will be the order of the new generator?)

3. Ex. 11.1

4. Ex. 11.2

5. Ex. 11.4 - extra credit (but it is highly recommended that you try to make as much progress on it as possible)

6. Ex. 11.12

7. Extra credit: Ex. 11.15

8. Extra super-credit: In class I have described an idea how space can be traded for time in an infinite loop detection. Section 11.2.5 in our textbook describes how similar space improvement can be achieved in the case of DLog. Try to understand this section and do as much of Ex.11.5-9 as you can. This might be easier  for those who already took cs237, as this section uses the probabilistic material outside of our scope in this course. Do this only after the rest of the problem set is done!