3 ms·
To be more specific: The only known things quantum computers are algorithmically superior for are factorization, computing discrete logarithms, and things that
by amalcon 14y ago
To be more specific: The only known things quantum computers are algorithmically superior for are factorization, computing discrete logarithms, and things that reduce to those. This happens to include all currently popular public-key cryptography. Fortunately, that is typically unrelated to symmetric-key cryptography.
At its core, to do public-key cryptography, you just need a difficult instance of an NP-but-non-P problem. Quantum computers put factorization and discrete logarithms into P, but there are still plenty of harder NP problems that have not been tapped. If quantum computing starts to become a significant threat, we'll probably see renewed interest in those.
- jessaustin 14y ago"an NP-but-non-P problem" Maybe I'm misunderstanding but if you had one of these you would have answered a fairly important question in CS theory. Perhaps you mean to say "NP-complete", but even then I'm not sure the proposition is correct.
- Dylan16807 14y agoIt's closer to "NP-but-not-weaker". NP-complete also means you can convert other NP problems into them, which isn't necessary.
- amalcon 14y agoYou're right that my statement wasn't specific enough; I was going for brevity. The precise statement is: You need a problem with a known polynomial-time nondeterministic algorithm, but no known polynomial-time deterministic algorithm.
- ReidZB 14y agoA very important point though: public-key cryptosystems rely on one-way functions, functions that are hard to invert in the average case, NOT just the worst case, which is not your typical complexity-theory mindset. So, I would be careful when talking about complexity classes in the context of crypto because it can be very, very easy to trip up and say something that's either not comprehensive or just downright incorrect.