Sunday, 14 November 2010

cryptography - The Discrete Logarithm problem

I am puzzled with the following discrete logarithm 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 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)$).



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!

No comments:

Post a Comment