4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Related: mathoverflow.net/questions/75089 $\endgroup$ – DES-SupportsMonicaAndTransfolk Mar 1 '13 at 15:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Yong Hao Ng Mar 2 '13 at 14:05
  • $\begingroup$ 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. $\endgroup$ – robjohn May 14 '13 at 13:06
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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