I'm trying to understand when there is a solution to the general DLP: given a, b, and n find x such that a^x == b (mod n). General in the sense that n can be any positive integer.
One algorithm is the baby-step giant-step algorithm. However this requires the calculation of a^-m which does not always exist.
My questions are:
- Under what conditions on
a,bandncan BSGS be used? - Are there sub-linear time algorithms that solve DLP under more general conditions?