Paper 2017/352

A low-resource quantum factoring algorithm

Daniel J. Bernstein, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2017
Keywords
post-quantum cryptographyfactorization
Contact author(s)
authorcontact-grovernfs @ box cr yp to
History
2017-04-26: received
Short URL
https://ia.cr/2017/352
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/352,
      author = {Daniel J.  Bernstein and Jean-François Biasse and Michele Mosca},
      title = {A low-resource quantum factoring algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2017/352},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/352}},
      url = {https://eprint.iacr.org/2017/352}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.