What algorithm to use to solve this simple mathematical problem efficiently?

Question

I am puzzled with the following simple 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

Thank you in advance!

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!

Answer 2

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.

Answer 3

as said the general problem is hard. however a prcatical way to find e if and only if you know e is going to be small (like in your example) would be just to try each e from 1.

btw e==3 is the first solution to your example, and you can obviously find that in 3 steps, compare to solving the non discrete version, and naively looking for integer solutions i.e.

e = log(c + n*m)/log(b) where n is a non-negative integer

which finds e==3 in 9 steps

Answer 4

>>> def find_e(b, c, m):
...     if b > m:
...         raise ValueError, "b must be less than m"
...     for val in b, c, m:
...         if type(val) != int:
...             raise ValueError, "All arguments must be ints"
...     return 7
...
>>> find_e(5, 8, 13)
7

This solves your example perfectly. Got any other homework I can do for you?

Answer 5

Yes its a discrete logarithm problem, as it is used in cryptographic algorithms, they are tough to break.