MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

closed as off topic by Reid Barton, Scott Morrison Dec 3 '09 at 6:59

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Google is your friend. Search for "discrete logarithm", which is what this problem is usually called. – Michael Lugo Dec 3 '09 at 0:36
Talking complexity theory, algorithms and the like, in programming're more likely to get a good response over at Stack Overflow than here, I think. – Charles Siegel Dec 3 '09 at 0:38
Do you want to deal with m a prime, or general m? If m is a prime, the wikipedia article 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 '09 at 0:41
@Charles: users of stackoverflow have directed me to the mathoverflow :) – psihodelia Dec 3 '09 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 '09 at 1:09
up vote 5 down vote accepted

The question is not phrased to our taste at mathoverflow, but the user has a point that this particular Wikipedia page is under-developed. As David Speyer suggests, it is a very different problem for very large primes than for small ones. For small primes the simplest algorithms described in Wikipedia are probably the most appropriate. If the question is instead about the theoretical time complexity, see this review article.

share|cite|improve this answer

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