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 n1.5 when factoring an n-bit number, rather than n2 as in Shor’s algorithm. The algorithm repeats that quantum part a few dozen times and combines the results to map out a high-dimensional lattice, from which it can deduce the period and factor the number. So the algorithm as a whole may not run faster, but speeding up the quantum part by reducing the number of required steps could make it easier to put it into practice.
Of course, the time it takes to run a quantum algorithm is just one of several considerations. Equally important is the number of qubits required, which is analogous to the memory required to store intermediate values during an ordinary classical computation. The number of qubits that Shor’s algorithm requires to factor an n-bit number is proportional to n, while Regev’s algorithm in its original form requires a number of qubits proportional to n1.5—a big difference for 2,048-bit numbers.
Again, this is all still theoretical. But now it’s theoretically faster.
Oded Regev’s paper.
This is me from 2018 on the potential for quantum cryptanalysis. I still believe now what I wrote then.
Subscribe to comments on this entry
Laverne • January 5, 2024 12:58 PM
To save everyone the math, this reduces the number of (logical quantum) steps by about 98% for 2048-bit or 4096-bit RSA. 92,700 steps instead of 4,200,000, for 2048 bits.