Skip to content

Comment on The NSA's crypto "breakthrough"parent

Comments

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.

Depends 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.)

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.