So as I understand it, quantum computers solve all NP problems in polynomial time. This means all encryption based on the distinction between P and NP, RSA being the most prominent, will be rendered useless.
My question is, are all public-key private-key algorithms rendered invalid? Could there possibly exists some algorithm that exploits the separation between, say, NP and PSPACE?
Yes, they are. No, there isn't.
Enjoy having your secret dataz stoled and your anus hax0red.
Name:
Anonymous2009-09-27 14:21
There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.
So as I understand it, quantum computers solve all NP problems in polynomial time.
Your understanding is incorrect.
This means all encryption based on the distinction between P and NP, RSA being the most prominent
Integer factorization that RSA is based on is believed not to be NP-complete.
Name:
Anonymous2009-09-27 18:23
>>1
A huge misconception about quantum computers is that quantum == exponential computing power. As six alluded to, this is the mainstream hollywood perception. I suggest you youtube some googletechtalk videos about this matter, as I am not an expertise, so I cannot give you a full answer.