Hacker News new | comments | show | ask | jobs | submit login

Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto?

Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of this when we observed the black holes of two galaxies colliding. So, even if it were possible it would still not matter. Practically speaking, it would still not be possible to travel back in time.

My gut feeling is that if it were to turn out that P==NP that would not necessarily mean that all of a sudden we would be able to find the exact algorithms that make it easy to crack cryptography algorithms easily.

We would know from the proof that such algorithms would exist, and possibly get a method from the proof as to how formulate them.

Also, gut feeling doesn't work in math. I mean, not at all.

NPC algorithms are roughly equivalent, so a P solution to one is a P solution to all. So, assuming the proof would be somewhat constructive, that would give you a P solution.

But, RSA (and probably other) cryptosystems aren't even thought to be NPC to solve... so they're probably unaffected. So, I guess it depends on the implementation details of the cryptosystem. Probably it wouldn't render them wide open, but it might make previously good keys far weaker, and mean that much longer must be spent on encryption for it to be safe (rather than now where a safe key can be decoded almost instantly on an embedded platform).

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact