8
$\begingroup$

Finding a discrete log in a finite cyclic group, like $(Z_N)^x$, seems hard and in some cases a solution may not even exist. Consider $N=15$ and the generator function $2^k=m \bmod 15$. This will produce the following values for $m$ given any non negative integer $k$...

$1, 2, 4, 8, 1, \dots$

Therefor, the equation $2^k=3 \bmod 15$ would have no (real?) solution. Is there a "fast" way of determining if any solution exists without factoring N?

  • 0
    If memory serves, computing the discrete logarithm is about as hard as factoring itself...2012-04-15
  • 0
    @J.M. That is correct but I'm asking about determining *if* a solution exists, not what the solution is. This seems like a subtle but important difference.2012-04-15
  • 0
    [Nitpicking.] In a cyclic group the discrete logarithm always exists (unless you picked a wrong base for the log). In $\mathbf{Z}_N^*$ it may not always exist, because the group in question is not always cyclic. [/Nitpicking] A good question! But how does factoring $N$ help us decide the answer? You seem to be implying that it would?2012-04-15
  • 0
    I'm convinced that the existence problem for discrete logs is as hard as the problem of finding discrete logs, but I'm not having much luck finding support for my conviction.2012-04-16
  • 0
    @JyrkiLahtonen if you wish to edit the question to be more exact in terminology, I wouldn't complain. As to the factoring of N, I may be wrong, but for some reason I thought that would help; however I seem to be having issues proving that now.2012-04-16
  • 0
    @GerryMyerson That's what I thought as well but I also couldn't find any references or proves that say otherwise. Which is why I posted the question.2012-04-16
  • 1
    Closest thing I've found is a paper by Kevin McCurley at http://www.mccurley.org/papers/dlog.pdf which says, "An alternative way to state the [discrete logarithm] problem is, Given $a,g$ in $G$, determine if there exists an integer $x$ such that $g^x=a$, and if so, find such an $x$. Note that this formulation of the problem might be harder to solve."2012-04-17
  • 0
    related: https://math.stackexchange.com/q/1301314/1632017-02-09

2 Answers 2