number theory - 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?