Search code examples
c++exponentiationmodular

Solving a modular exponentiation with unknown power


Guys I what is the fastest algorithm to solve a modular equation in the format of a^b = c mod p where p is a really big prime and b is unknown. e.g.:

2^k = 15 mod 30903154482632612361920641803533

I already tried trial and error using boost library in C++ but it would take very long time to reach the answer.


Solution

  • You're trying to solve what is called a discrete logarithm. If there was an efficient solution to this, I imagine whoever discovered it would wreak chaos on cryptographic systems long before it would be posted here.

    You will find quite a couple of algorithms on Wikipedia with varying time complexity. Some of these are quite easy to implement. See The computational complexity of discrete log for the best space complexity.