3 ms·

I think the complexity class of discrete log or integer factorization are not known. No one has proved there isn't a polynomial time algorithm but if one is fo

• nhaehnle 13y ago
  This is true. However, this actually means that the type of proof that kazagistar asked for is harder than a proof that P != NP. After all, if you prove that factorization cannot be done in polynomial time, then a corollary of this result is that P != NP. Intuitively, NP-hard problems are believed to be harder than factorization and discrete log. And so it should be easier to prove that an NP-hard problem is not in P. What you are referring to is the opposite direction of the implication, which is very relevant in a discussion of why people have failed to find faster algorithms for integer factorization. However, the question I replied to is essentially why people have failed to prove that integer factorization (and discrete log) are hard problems. Edit: After re-reading my previous comment, perhaps this clarifies it best: Integer factorization and discrete log are probably less hard than NP-hard problems. However, the meta-problem "prove that integer factorization or discrete log is really, unconditionally hard" is at least as difficult as the meta-problem "prove P != NP".