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?

  • $\begingroup$ DL is hard for prime moduli as long as $n-1$ has certain properties. We typically use primes for Diffie-Hellman or DSA. $\endgroup$ Aug 5, 2013 at 8:14

1 Answer 1


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$.

The reason for this assumption are algorithms like Pohlig-Hellman and Index Calculus. If the multiplicative group order has only small factors, then the problem becomes much easier.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.