[Resource Topic] 2017/352: A low-resource quantum factoring algorithm

Welcome to the resource topic for 2017/352

A low-resource quantum factoring algorithm

Authors: Daniel J. Bernstein, Jean-François Biasse, Michele Mosca


In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just (\log N)^{2/3+o(1)} qubits to factor an integer N in time L^{q+o(1)} where L = \exp((\log N)^{1/3}(\log\log N)^{2/3}) and q=\sqrt[3]{8/3}\approx 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is L^{p+o(1)} where p>1.9. The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.

ePrint: https://eprint.iacr.org/2017/352

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .