2 ms·
As you might expect, it's not as simple as that. There are caveats about the degree of the polynomial (n^1000 is pretty fast growing) and we'e pretty sure fact
by RiderOfGiraffes 16y ago
As you might expect, it's not as simple as that. There are caveats about the degree of the polynomial (n^1000 is pretty fast growing) and we'e pretty sure factoring isn't in NPC anyway.
But if P==NP then there is a polynomial factoring algorithm that we haven't yet found, and that would probably be bad for current public-key crypto.
The current result seems to say that P!=NP, so at least it's still plausible, even likely, that there's no polynomial factoring algorithm.