schoen, Pseudonym, and yakk: Thanks for your input. I knew that factoring was in NP (although nobody is able to prove that there is NOT an algorithm in P). I was under the mistaken impression that it might be NP-complete as well. So finding a P algorithm for factoring won't show that P=NP as I erroneously suggested.

I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?

I have found that Sipser's "Introduction to the Theory of Computation" is a good primer for all of this, for those that are curious. Now to work on a provably EXPTIME-hard encryption method. I think I can bang one out this weekend. ;)