# Efficiently determining if a discrete log exists

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?

-
If memory serves, computing the discrete logarithm is about as hard as factoring itself... – J. M. Apr 15 '12 at 15:12
@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. – Andrew White Apr 15 '12 at 15:31
[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? – Jyrki Lahtonen Apr 15 '12 at 16:13
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. – Gerry Myerson Apr 16 '12 at 0:47
@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. – Andrew White Apr 16 '12 at 14:27

I don't know of a fast way to solve the decision version of discrete log. Your intuition that factoring would be useful was correct; there is a efficient reduction to factoring $n$.
Given $a^x=b \bmod n$ for known $a$,$b$ to tell if a solution exists:
(1) Factor the modulus into prime powers. By the Chinese remainder theorem a solution exists iff it exists mod each prime power (2) For each of these factor $p$-1 (3) Compute the order of $a$ and $b$ mod $p^k$ using the factorization of $p$-1 (can be done quickly using a generalization of Euler's criterion) (4) A solution exists iff the order of $b$ divides the order of $a$.
Misc remarks: (1) It is unknown if factoring $n$ reduces to being able to solve the decision discrete log mod $n$. (2) Its not hard to show factoring $n$ reduces to the computational version of discrete log mod $n$ (discrete log can be used to compute the order of any element mod $n$ and there is a well known way to factor $n$ given this. It's described on the Wikipedia page for Shor's algorithm). (3) Given the factors of $n$, discrete log mod $n$ reduces to discrete log mod $p$. It is unknown if a fast method for factoring any number would imply that the discrete log mod primes can also be solved quickly.