3 ms·
Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't ge
by cschmidt 13y ago
Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't get P=NP from any factoring breakthrough.
- yk 13y agoDepends on the breakthrough, we know that multiplication is in P and therefore factorization in NP. So a P?=NP breakthrough may or may not have consequences for integer factorization. ( Actually since I did write that, I wonder if P=NP would invalidate any public key crypto, since efficient encryption should be in P.)