I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]).

The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up factoring (at least not in a way that makes it polynomial).

[1] https://en.wikipedia.org/wiki/Reduction_(complexity)

[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm

(EDIT: typo)

That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.

The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor:

* fastest known method for DLP is O(exp(c sqrt(log n log log n)))

* 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n"

Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply.

See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered".

[1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...