0
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • $\begingroup$ Google is your friend. Search for "discrete logarithm", which is what this problem is usually called. $\endgroup$
    – Michael Lugo
    Commented Dec 3, 2009 at 0:36
  • $\begingroup$ 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. $\endgroup$
    – Charles Siegel
    Commented Dec 3, 2009 at 0:38
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Dec 3, 2009 at 0:41
  • $\begingroup$ @Charles: users of stackoverflow have directed me to the mathoverflow :) $\endgroup$
    – psihodelia
    Commented Dec 3, 2009 at 0:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alon Amit
    Commented Dec 3, 2009 at 1:09

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .