Slightly Wrong Discrete Log Problem

• Recall that in showing that hardness of the Discrete Log Problem implies collision resistance of the Discrete Log Hash Family we only showed how to solve Dlog_x(y) mod p when both x and y are primitive. No method of solution was provide when y was non-primitive, as allowed in the general Dlog problem. (For the case p = 2q + 1, q prime, this implied failure to solve Dlog for about half of all cases). Suppose a number ε has been found such that:

  For each non-primitive n ∈ Z_p* , the conditional probability Prob( mn is primitive   |   m is primitive ) > ε

  Let δ denote the probability that a randomly chosen element in Z_p* is primitive.
  1. (8 pts.) Show that if Dlog is solvable by a deterministic algorithm when x and y are primitive, then a Las-Vegas algorithm with probability > δε for success can be given for solving the general Dlog problem.
  2. (2 pts.) Calculate ε for p = 2q + 1, where p, q are prime.
  3. (EC 10 pts.) Find a formula for &epsilon which works for all primes p (the formula may depend on the factorization of p). Prove your formula.