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. :) _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
