3 ms·

So if P = NP, that would be a problem for RSA as in theory there would be a quick way of factoring your big number (even if no-one has yet discovered how to do

• 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.
• teilo 16y ago
  No, not really. P != NP should be read: It is not true that for every NP, there is a P, but for any specific P problem, there MAY be an NP solution unless you can prove otherwise. This is a classic syllogism: All tigers are cats, but not all cats are tigers. Similarly, if P != NP, you can say, there absolutely, and provably, are solutions which are hard to solve, but easy to validate. However, this fact alone does not tell you if your problem is that way. If P=NP were true, you could consider every public-key cryptographic system to be a ticking time-bomb. It's only a matter of time before someone find's the easy solution that breaks the entire system irrevocably, because such a solution absolutely does exist if P=NP. P != NP is status quo. It means: Breathe easy, folks. Your cryptography systems may not be provably secure, but they are certainly not provably unsecure as a category.