Security News > 2024 > January > Improving Shor’s Algorithm
![Improving Shor’s Algorithm](/static/build/img/news/alt/web-statistics-medium.jpg)
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.
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.
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.
News URL
https://www.schneier.com/blog/archives/2024/01/improving-shors-algorithm.html