4 ms·
No. Public key cryptography is impossible if P=NP. What we are left with is shared one-time-pads that can be arranged using quantum key distribution. I am not
by blendergeek 4y ago
No. Public key cryptography is impossible if P=NP. What we are left with is shared one-time-pads that can be arranged using quantum key distribution.
I am not an expert so I will simply link the Wikipedia article on Computational Complexity Theory as my "source".
https://en.m.wikipedia.org/wiki/Computational_complexity_theory https://en.m.wikipedia.org/wiki/Computational_complexity_the...
- bwesterb 4y agoIf there is an n^(100^100) algorithm that solves an NP-complete problem, then P=NP, but public-key cryptography is still safe because for any practical n it's still too hard to break. There are also public-key systems that are based on NP-complete problems that are easily broken, because n is chosen too small.
- blendergeek 4y agoThank you for schooling me on this. I wasn't considering n^(100^100) problems.