**A low-resource quantum factoring algorithm**

*Daniel J. Bernstein and Jean-François Biasse and 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.

**Category / Keywords: **public-key cryptography / post-quantum cryptography, factorization

**Original Publication**** (in the same form): **PQCrypto 2017

**Date: **received 19 Apr 2017

**Contact author: **authorcontact-grovernfs at box cr yp to

**Available format(s): **PDF | BibTeX Citation

**Version: **20170426:172406 (All versions of this report)

**Short URL: **ia.cr/2017/352

[ Cryptology ePrint archive ]