Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 2 more comments

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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