Finding x in $a^{x} \bmod b = c$ when values a,b, and c are known?
If values $a$, $b$, and $c$ are known, is there an efficient way to find $x$ in the equation: $a^{x} \bmod b = c$?
E.g. finding $x$ in $128^{x}\bmod 209 = 39$.
Solution 1:
This is the Discrete Logarithm Problem. If by "efficient" you mean "polynomial time general purpose algorithm", the answer is that none are known.
Solution 2:
A better reference than Wikipedia for the discrete logarithm problem is Andrew Sutherland's 2007 MIT Thesis Order Computations in Generic Groups. Here's an excerpt from p. 14 that provides a concise summary of the current state of knowledge.
