# Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

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?

#### Solutions Collecting From Web of "Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$"

If $\gcd(a,n)=g>1$ then if $g\nmid b$ there’s clearly no solution. Otherwise write $a=g\alpha$, $b=g\beta$, $n=g\nu$, so
$$a^x\equiv b\pmod{n} \iff g^{x-1}\alpha^x\equiv \beta \pmod{\nu}$$
Since $\gcd(\alpha,\nu)=1$, $\alpha$ has an inverse mod $\nu$. Divide through by $\alpha$ to get
$$(g\alpha)^{x-1} = a^{x-1} \equiv \beta\alpha^{-1} \pmod{\nu}$$
If $\gcd(a,\nu)=1$ then you can use your preferred algorithm for the relatively prime case, otherwise repeat this reduction.

Example 1: $6^x \equiv 4 \pmod{44}$

Using $3\cdot 15 \equiv 1 \pmod{22}$ and $3\cdot 4 \equiv 1 \pmod{11}$:
\begin{align} 2^{x-1}3^x & \equiv 2 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 8 \pmod{22} \\ 2^{x-2}3^{x-1} & \equiv 4 \pmod{11} \\ 6^{x-2} & \equiv 4\cdot4 \equiv 5 \pmod{11} \\ \end{align}
Now $\gcd(6,11)=1$, so if you can solve this you might get $x-2=6$, $x=8$.

Example 2: $6^x \equiv 2 \pmod{44}$

Starting as in Example 1:
\begin{align} 2^{x-1}3^x & \equiv 1 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 15 \pmod{22} \\ \end{align}
and this has no solution since $\gcd(6,22) \nmid 15$.

This is very incomplete.

Since there are only a finite number of elements, eventually the sequence {ak mod n}k$\ge$0 must become cyclic. So there are natural numbers $\sigma$ and $\lambda$ such that a$\sigma$ + v$\lambda$ = a$\sigma$ for all v.

So there are exactly two elements where you can’t calculate the element that came before it like you can in a cyclic group. The first is obviously 1 itself, the second is the first element of the cyclic part which is equal to both a$\sigma$-1a and a$\sigma$+$\lambda$-1a.

The problem is I think $\sigma$ can approach n so we’d spend all our time moving along the tail.