From Schneier on Security – Improving Shor’s Algorithm

We don’t have a useful quantum computer yet, but we do have quantum algorithms. Shor’s algorithm has the potential to factor large numbers faster than otherwise possible, which—if the run times are actually feasible—could break both the RSA and Diffie-Hellman public-key algorithms.
Now, computer scientist Oded Regev has a significant speed-up to Shor’s algorithm, at the cost of more storage.
Details are in this article. Here’s the result:
The improvement was profound. The number of elementary logical steps in the quantum part of Regev’s algorithm is proportional to … Read More