4 ms·
I thought there were concerns about public key cryptography - factoring large numbers much faster with QC at least sounds plausible, but maybe it’s just specula
by jeremyjh 4y ago
I thought there were concerns about public key cryptography - factoring large numbers much faster with QC at least sounds plausible, but maybe it’s just speculation ?
- tsimionescu 4y agoThat is true, but integer factorization is not an NP-hard problem, as far as we know at least. A quantum algorithm, Shor's algorithm, is indeed known to be able to solve it in polynomial time if you have a QC. It is suspected to be NP but not even NP-complete, nevermind NP-hard. It is suspected not to be in P, but that is not yet proven.
- kragen 4y agoInteger factorization is obviously in NP, though as you say, whether it is in the P subset of NP is still an open question.
- tsimionescu 4y agoI was trying to be careful with my language specifically to avoid this mistake, but I still messed up...
- kragen 4y agoIt's tricky!
- PeterisP 4y agoWe're moving on to quantum-resistant public key cryptography, so unless some QC hardware breakthrough appears really soon, we'd expect quantum computers to be useless against public key cryptography because we won't rely on the difficulty of factoring large numbers as a security measure by the time large enough quantum computers appear.