most recent 30 from http://mathoverflow.net 2013-05-19T12:57:32Z http://mathoverflow.net/feeds/question/7624 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7624/the-discrete-logarithm-problem psihodelia 2009-12-03T00:25:18Z 2009-12-03T01:04:28Z

<p>I am puzzled with the following discrete logarithm problem:</p> <p>Given positive integers <code>b, c, m</code> where <code>(b &lt; m) is True</code> it is to find a positive integer <code>e</code> such that</p> <pre><code>(b**e % m == c) is True </code></pre> <p>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)$). </p> <p>What is the most effective algorithm (with the lowest big-O complexity) to solve it ?</p> <p>Example: Given b=5; c=8; m=13 this algorithm must find e=7 because 5**7%13 = 8</p> <p>Thank you in advance!</p>

http://mathoverflow.net/questions/7624/the-discrete-logarithm-problem/7629#7629 Greg Kuperberg 2009-12-03T01:04:28Z 2009-12-03T01:04:28Z

<p>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 <a href="http://www.math.leidenuniv.nl/~psh/ANTproc/12oliver.pdf" rel="nofollow">this review article</a>.</p>