Back

Low qubit-resource quantum factoring

"”A low-resource quantum factoring algorithm"

Published by Daniel J. Bernstein, Jean-François Biasse, and Michele Mosca (Univ. of Illinois, Eindhoven Univ., Univ. of South Florida, Univ. of Waterloo, Perimeter Institute, Canadian Institute for Advanced Research), 3rd June 2017

Cr.yp.to
Cryptography
Low qubit-resource quantum factoring

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.