# What is the (classical) algorithm of choice for finding discrete logarithms in composite-moduli groups?

I've recently written an answer on how to find the factorization of a $n$ if we can find the order(s) of elements in the associated group $\mathbb Z_n^*$. This also lead me to Shor's algorithm which does basically just that: Find the order and then compute the factorization from that.

Now, probably for a learning experience, I've thought about implementing the above factorization method but I'm short of an algorithm to find the discrete logarithm in the generic $\mathbb Z^*_n$ group without factoring $n$ first.

So what is the algorithm with the best run-time complexity that can find discrete logarithms in $\mathbb Z^*_n$ for $n\in\mathbb N_{\geq 2}$ without factoring $n$ first?

• The ring is $\mathbf{Z}_n$; $\mathbf{Z}_n^*$ is its (multiplicative) group of units. ;) Dec 15, 2016 at 16:13

Suppose you had a discrete log oracle giving $$\mathcal O(n, g, g^x) \equiv x \pmod{\phi(n)}$$ with high probability for random $$g$$ and $$x$$. Pick a uniform random $$g$$ and a large random prime $$k$$; let $$m = \mathcal O(n, g^k, g)$$, so that $$(g^k)^m \equiv g \pmod n,$$ or $$g^{k m - 1} \equiv 1 \pmod n;$$ then the order of $$g$$ modulo $$n$$ divides $$k m - 1$$. This gives an oracle to find the order of a random element (or some multiple of it). As you observed, this is enough to factor $$n$$ with modest additional effort.
Hence any algorithm you can use to compute discrete logs modulo a composite $$n$$ can't be much cheaper than an algorithm to factor $$n$$: there can't be much to be gained by attacking discrete logs directly. So it's not surprising that the state of the art for both is some variant of the GNFS.