Welcome to the resource topic for
**2017/352**

**Title:**

A low-resource quantum factoring algorithm

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

**Abstract:**

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 .