Quantum Computing Not an Imminent Threat To Public Encryption

Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.

Comments

Re:Schneier knows his stuff

[gomiam]

Perhaps you would like to read again what NP-complete means: being able to quickly check (read: in polynomial time) whether a solution is right or not by using a deterministic algorithm. Quantum computers are non-deterministic, and that's why they can be used to factor large integers. "Check all periods of r so a^r=1 (mod N) at the same time" certainly isn't deterministic.

The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.

You might as well conclude that grass is purple, for all the sense that paragraph makes.