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 n 1.5 when factoring an n-bit number, rather than n 2 as [...]