The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. But when $\gcd(a,n) \neq 1,$ it is not possible to compute $a^{-1}\pmod{n},$ which the algorithm requires.
What algorithms are available to solve this problem in this case (apart from brute force of course)? Are there any theoretical limits on how fast such an algorithm could run?