Shor's Algorithm (Re:Security through openness) (Score 2)

Actually, if you stretch your definitions a little, somebody has found an efficient factoring algorithm. Peter Shor's algorithm will factor a number in polynomial time, trouble is it only works on a quantum computer.

It's been proven that P QP (that is, the set of all classical polynomial-time problems is a subset of all quantum polynomial-time problems) Also, there are certain things that can be done on quantum computers more efficiently than a classical computer could (not just speculation, there are problems like this)

I wish I knew more about this stuff.