A low-resource quantum factoring algorithm

D.J. Bernstein; J. F. Biasse; M. Mosca

doi:10.1007/978-3-319-59879-6_19

A low-resource quantum factoring algorithm

D.J. Bernstein
, J. F. Biasse
, M. Mosca

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

14 Citations (Scopus)

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 =³√8/3 ≈ 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.

Original language	English
Title of host publication	Post-Quantum Cryptography
Subtitle of host publication	8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings
Editors	T. Lange, T. Takagi
Place of Publication	Dordrecht
Publisher	Springer
Pages	330-346
Number of pages	17
ISBN (Print)	978-3-319-59879-6 19
DOIs	https://doi.org/10.1007/978-3-319-59879-6_19
Publication status	Published - 2017
Event	8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017) - Utrecht, Netherlands Duration: 26 Jun 2017 → 28 Jun 2017 Conference number: 8 https://2017.pqcrypto.org/conference/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10346 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017)
Abbreviated title	PQCrypto 2017
Country/Territory	Netherlands
City	Utrecht
Period	26/06/17 → 28/06/17
Internet address	https://2017.pqcrypto.org/conference/

Access to Document

10.1007/978-3-319-59879-6_19

Cite this

Bernstein, D. J., Biasse, J. F., & Mosca, M. (2017). A low-resource quantum factoring algorithm. In T. Lange, & T. Takagi (Eds.), Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings (pp. 330-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10346 LNCS). Springer. https://doi.org/10.1007/978-3-319-59879-6_19

Bernstein, D.J. ; Biasse, J. F. ; Mosca, M. / A low-resource quantum factoring algorithm. Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings. editor / T. Lange ; T. Takagi. Dordrecht : Springer, 2017. pp. 330-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{720c755319aa407aae21541ae63e3b50,

title = "A low-resource quantum factoring algorithm",

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 Lq+o(1) where L = exp((log N)1/3 (log log N)2/3) and q =3√8/3 ≈ 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is Lp+o(1) where p > 1.9. The new time complexity is asymptotically worse than Shor{\textquoteright}s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.",

author = "D.J. Bernstein and Biasse, \{J. F.\} and M. Mosca",

year = "2017",

doi = "10.1007/978-3-319-59879-6\_19",

language = "English",

isbn = "978-3-319-59879-6 19",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "330--346",

editor = "T. Lange and T. Takagi",

booktitle = "Post-Quantum Cryptography",

address = "Germany",

note = "8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017), PQCrypto 2017 ; Conference date: 26-06-2017 Through 28-06-2017",

url = "https://2017.pqcrypto.org/conference/",

}

Bernstein, DJ, Biasse, JF & Mosca, M 2017, A low-resource quantum factoring algorithm. in T Lange & T Takagi (eds), Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10346 LNCS, Springer, Dordrecht, pp. 330-346, 8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017), Utrecht, Netherlands, 26/06/17. https://doi.org/10.1007/978-3-319-59879-6_19

A low-resource quantum factoring algorithm. / Bernstein, D.J.; Biasse, J. F.; Mosca, M.
Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings. ed. / T. Lange; T. Takagi. Dordrecht: Springer, 2017. p. 330-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10346 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A low-resource quantum factoring algorithm

AU - Bernstein, D.J.

AU - Biasse, J. F.

AU - Mosca, M.

N1 - Conference code: 8

PY - 2017

Y1 - 2017

N2 - 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 Lq+o(1) where L = exp((log N)1/3 (log log N)2/3) and q =3√8/3 ≈ 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is Lp+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.

AB - 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 Lq+o(1) where L = exp((log N)1/3 (log log N)2/3) and q =3√8/3 ≈ 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is Lp+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.

UR - https://www.scopus.com/pages/publications/85021752448

U2 - 10.1007/978-3-319-59879-6_19

DO - 10.1007/978-3-319-59879-6_19

M3 - Conference contribution

AN - SCOPUS:85021752448

SN - 978-3-319-59879-6 19

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 330

EP - 346

BT - Post-Quantum Cryptography

A2 - Lange, T.

A2 - Takagi, T.

PB - Springer

CY - Dordrecht

T2 - 8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017)

Y2 - 26 June 2017 through 28 June 2017

ER -

Bernstein DJ, Biasse JF, Mosca M. A low-resource quantum factoring algorithm. In Lange T, Takagi T, editors, Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings. Dordrecht: Springer. 2017. p. 330-346. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59879-6_19

A low-resource quantum factoring algorithm

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this