I am a bit confused on the hardness of the discrete logarithm problem. Does it become intractale only when it is mod n, where n is a large composite number (Like RSA key). What about if it is mod a prime number p? what is the complexity and method for solving it? Can we reduce the problem of integer factorization to discrete log problem and vice versa?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The discrete logarithm problem is usually only considered in prime groups. And there $p-1$ has to have at least one large prime factor.
Composite moduli are usually used for RSA problem (related to factorization), quadratic residuosity or composite residuosity. The hardness of these assumptions depends on the fact that the order of the multiplicative groups are not known (the factorization can be calculated from this order directly).
In general, the discrete logarithm problem could be considered in composite groups, and there you would require the totient $\phi(n)$ to have at least one large prime factor. The reason for this is, that the order of the multiplicative group mod n is $\phi(n)$. In prime order groups this happens to be $p-1$.