|
|
|
|
|
by dvdkhlng
2552 days ago
|
|
I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength. 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... |
|