# 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?

-
BTW did you check Henri Cohen's book Computational Algebraic Number Theory to see if such case is there? – user2468 Apr 13 '12 at 1:56
If you have a "fairly quick" way to compute discrete logarithms in the $a$, $n$ coprime case, you should be out there making a name for yourself demolishing cryptographic algorithms. – Henning Makholm Apr 13 '12 at 22:22

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.

-