Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
DL is hard for prime moduli as long as $n-1$ has certain properties. We typically use primes for Diffie-Hellman or DSA. –  CodesInChaos Aug 5 '13 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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