5
$\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$
3
  • $\begingroup$ Related: mathoverflow.net/questions/75089 $\endgroup$
    – David E Speyer
    Mar 1, 2013 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, 2013 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, 2013 at 13:06

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .