## The Discrete Logarithm problem [closed]

I am puzzled with the following discrete logarithm problem:

Given positive integers b, c, m where (b < m) is True it is to find a positive integer e such that

(b**e % m == c) is True


where two stars is exponentiation (e.g. in Ruby, Python or ^ in some other languages) and % is modulo operation. Using general math symbols it looks like:($b^e \equiv c (\mod m)$).

What is the most effective algorithm (with the lowest big-O complexity) to solve it ?

Example: Given b=5; c=8; m=13 this algorithm must find e=7 because 5**7%13 = 8

Thank you in advance!

-
Google is your friend. Search for "discrete logarithm", which is what this problem is usually called. – Michael Lugo Dec 3 2009 at 0:36
Talking complexity theory, algorithms and the like, in programming language...you're more likely to get a good response over at Stack Overflow than here, I think. – Charles Siegel Dec 3 2009 at 0:38
Do you want to deal with m a prime, or general m? If m is a prime, the wikipedia article en.wikipedia.org/wiki/Discrete_logarithm is quite detailed. Note that many of the algorithms there are only worth implementing for m in the 10's of digits. – David Speyer Dec 3 2009 at 0:41
@Charles: users of stackoverflow have directed me to the mathoverflow :) – psihodelia Dec 3 2009 at 0:51
@psihodella: The trouble with this question is that it's not asking for anything that's not *widely* documented in the literature. Of course, the most effective algorithm may not be known to anyone, but the known algorithms are easy to find details on. The Wikipedia article refers to several algorithms and, if you follow the links, you'll find information on their running time. – Alon Amit Dec 3 2009 at 1:09
show 3 more comments