Calculate discrete logarithm
algorithm, math
Solution
This isn't a simple problem at all. It is called calculating the discrete logarithm and it is the inverse operation to a modular exponentation.
There is no efficient algorithm known. That is, if N denotes the number of bits in m, all known algorithms run in O(2^(N^C)) where C>0.
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 ** 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