You are looking at a specific version 20170426:172406 of this paper. See the latest version.

Paper 2017/352

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.

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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.