>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial
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.
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.