3.4.9 What is the discrete log problem?

  The discrete log problem, in its most common formulation, is to find the exponent x in the formula y=g^x mod p; in other words, it seeks to answer the question, To what power must g be raised in order to obtain y, modulo the prime number p? There are other, more general, formulations as well.

Like the factoring problem, the discrete log problem is believed to be difficult and also to be the hard direction of a one-way function. For this reason, it has been the basis of several public-key cryptosystems, including the ElGamal system and DSS (see Questions 3.2.15 and 3.6.8). The discrete log problem bears the same relation to these systems as factoring does to RSA: the security of these systems rests on the assumption that discrete logs are difficult to compute.

The discrete log problem has received much attention in recent years. The best discrete log problems have expected running times similar to that of the best factoring algorithms. Rivest has analyzed the expected time to solve discrete log both in terms of computing power and money.