Qu&Co comments on this publication:
Shor's algorithm for breaking both RSA and discrete-log public-key cryptography depend on the availability of a relatively large-scale quantum computer (e.g. Kutin et al. showed in 2006 that factoring a 1024-bit number requires 3132 qubits and 5.7x10^9 T gates). However, in quantum hardware developments are progressing while at the same time quantum algorithms are getting more efficient. So the timing when quantum computers will be able to break e.g. RSA is shifting. In this paper, Berstein et al. present a factoring algorithm that, assuming standard heuristics, uses a sublinear number of qubits. The time complexity of their new algorithm is asymptotically worse than Shor's algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement the new algorithm sooner than Shor's algorithm.