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

Question

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?

Answer 1

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.