RSA Weak?

[Robert J. Hansen]

Sven Radde wrote:
> In fact, some mathematician has proven that factoring is a polynomial
> problem, IIRC.

Well, we know it's in NP, since polytime verification is possible; and
there are strong arguments that it cannot be NP-HARD, because then it
would exist in both NP and Co-NP, which would lead to various proofs
that would collapse an awful lot of mathematics as we know it.

It's been (trivially) proven factoring exists in NP and also in Co-NP.
The open question is whether it is NP-HARD or Co-NP-HARD.  If it's
NP-HARD, then everybody is in a whole lot of trouble; a proof of
NP-HARDness would nead to a proof that factoring was NP-Complete, which
would mean that NP = Co-NP.  I'm blanking on precisely the consequences
after that, but I do recall that if NP = Co-NP then a lot of our
commonsense understanding of math gets turned on its ear.

I guess you could say we believe factoring is not NP-HARD because the
consequences of it being so are too catastrophic to consider.  :)