# Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all?

With the discrete logarithm problem I mean the following problem:

Let $G$ be a group and let $g$ and $h$ be elements of $G$ such that $h \in \langle g \rangle$. Find an integer $x$ such that $g^x = h$.

In particular I am interested in the case where $G = \mathbb{Z}_p^*$. If we know an efficient way to factor integers, does this help us in solving the discrete logarithm problem for a given $\mathbb{Z}_p^*$?

Conversely, if we know how to solve the discrete logarithm problem efficiently for any group $G$ (or just $\mathbb{Z}_p^*$), does this help with factoring integers?

• Related: mathoverflow.net/questions/75089 – DES-SupportsMonicaAndTransfolk Mar 1 '13 at 15:13
• I am not so sure about your definition of "help". For instance, if you can factor integers in polynomial time then certainly you can solve discrete logarithm in $\mathbb{Z}_p^*$ in a faster time. This is because modern algorithms devote a significant amount of computation on factoring medium sized integers during a phase called "sieving". So if you are just asking about speedup in general then answer is affirmative ($\mathbb{Z}_p^*$). Your last question is answered in the MO article ($\mathbb{Z}_p^*$). DL on general Elliptic Curves is still open to my best of knowledge. – Yong Hao Ng Mar 2 '13 at 14:05
• It has been suggested that this be migrated to crypto. Although this question is important to cryptology, it definitely seems to be a math problem, too. I suggest we leave it here for now. If it doesn't get a good answer in a while, we can think about migrating. – robjohn May 14 '13 at 13:06

Are these two problems related at all?

The answer is yes, and it is at many levels. The general number field sieve, which is generally thought of as a factoring algorithm, is also very useful for solving discrete logs.

Theoretically: Solving the discrete log with a composite modulus is exactly as hard as factoring [3]. However, it is not known if solving discrete log with a prime modulus leads to efficient factoring [4].

If we know an efficient way to factor integers, does this help us in solving the discrete logarithm problem for a given $\mathbb{Z}_p^*$?

Conversely, if we know how to solve the discrete logarithm problem efficiently for any group G (or just $\mathbb{Z}_p^*$), does this help with factoring integers?

For composite modulus, the answer is yes. For prime modulus, we don't know.

A good reference for a lot of this information is John Gregg's thesis page 43.