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?