Calculate discrete logarithm

Question

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 ** is exponentiation (e.g. in Ruby, Python or ^ in some other languages) and % is modulo operation. 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

Answer 1

From the % operator I'm assuming that you are working with integers.

You are trying to solve the Discrete Logarithm problem. A reasonable algorithm is Baby step, giant step, although there are many others, none of which are particularly fast.

The difficulty of finding a fast solution to the discrete logarithm problem is a fundamental part of some popular cryptographic algorithms, so if you find a better solution than any of those on Wikipedia please let me know!