Can anyone tell me how to solve this equation for lowest $x$
$$a^x \equiv n \mod m$$
other than trying every possible $x$ from $0$ to $m-1$ ($m$ is prime)?
Asked
Active
Viewed 1,272 times
3
-
It is a hard problem, discrete logarithm. As far as I know, one can do better than plain brute force, but no efficient general algorithm is known. – Daniel Fischer Oct 05 '13 at 18:12
-
How much hard,can you suggest some heuristic etc.what if everything falls into lets say 32 bit range. – Amit Oct 05 '13 at 19:16
-
http://en.wikipedia.org/wiki/Discrete_logarithm – Van Jone Oct 06 '13 at 01:50
1 Answers
2
This is known as the discrete logarithm problem, and it's a hard problem. By hard, I mean that it's an NP (in the P$\neq$NP sense) problem.
So the short answer is that for anything of any reasonably small size, you should just do trial division.
For slightly larger ones, there are a variety of slightly-faster-but-still-slow algorithms, such as a variant of Pollard's rho algorithm for factoring, or the cutely titled baby-step giant-step algorithm.
davidlowryduda
- 91,687