The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
An Efficient Quantum Factoring Algorithm
Open accessAbstract
We show that n -bit integers can be factorized by independently running a quantum circuit with \(\tilde{O}(n^{3/2})\) gates for \(\sqrt {n}+4\) times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The gap between required secrecy lifetime and the adversary's horizon is shrinking as advances in quantum computation reduce the time needed to break cryptosystems such as RSA and elliptic-curve cryptography.
“The gap between these two quantities is shrinking as advances in quantum computation reduce the time needed to break cryptosystems such as RSA and elliptic-curve cryptography [31,32].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [32]
Large-scale factoring of RSA-2048 on a fault-tolerant quantum computer requires deep logical circuits and extensive error correction, demanding millions of physical qubits and prolonged error-free operation.
“large-scale factoring of RSA-2048 on a fault-tolerant quantum computer requires deep logical circuits and extensive error correction, demanding millions of physical qubits and prolonged error-free operation [1,2,31,32].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [32]
Citations
Cites
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers
Ekerå, M., & Håstad, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-59879-6_20 · Cited by 62
On post-processing in the quantum algorithm for computing short discrete logarithms
Ekerå, M. (2020) · Designs, Codes and Cryptography · doi:10.1007/s10623-020-00783-2 · Cited by 23
Flagged first, then by citations
Research works printed but not linked: 17
- 10.1007/BF01445125 · DOI
- Huck Bennett, Daniel Dadush, and Noah Stephens-Davidowitz. 2016. On the lattice distortion problem. In Proceedings of the 24th Annual European Symposium on Algorithms. LIPIcs. Leibniz International Proceedings in Informatics, Vol. 57, Schloss Dagstuhl. Leibniz Zentrum für Informatik, Wadern, Art. No. 9, 17.
- 10.1109/SFCS.2000.892140 · DOI
- Don Coppersmith. 1994. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067. Retrieved from https://arxiv.org/abs/quant-ph/0201067 · arXiv
- 10.1007/s10623-018-0573-3 · DOI
- 10.1007/978-3-658-00360-9 · DOI
- Martin Ekerå and Joel Gärtner. 2024. Extending Regev’s factoring algorithm to compute discrete logarithms. In Post-Quantum Cryptography Springer Nature Switzerland Markku-Juhani Saarinen and Daniel Smith-Tone (Eds.). Cham 211–242. · DOI
- Martin Ekerå and Joel Gärtner. 2024. A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography. arXiv:2405.14381. Retrieved from https://arxiv.org/abs/2405.14381 · arXiv
- 10.1145/1374376.1374408 · DOI
- Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph/0208112. Retrieved from https://arxiv.org/abs/quant-ph/0208112 · arXiv
- 10.4007/annals.2021.193.2.4 · DOI
- Cédric Pilatte. 2024. Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms. arXiv:2404.16450. Retrieved from https://arxiv.org/abs/2404.16450 · arXiv
- 10.1137/0209022 · DOI
- 10.1023/A:1015250102792 · DOI
- Seyoon Ragavan and Vinod Vaikuntanathan. 2024. Space-efficient and noise-robust quantum factoring. In Advances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference Santa Barbara CA USA August 18–22 2024 Proceedings Part VI Springer-Verlag Santa Barbara CA USA 107–140. DOI:10.1007/978-3-031-68391-6_4 · DOI
- 10.1145/1568318.1568324 · DOI · Paper page
- 10.1007/3-540-45353-9_24 · DOI
Cited by
Sorted by citations
Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition
Kagai, F., Branch, P., But, J., & Allen, R. (2025) · Telecom · doi:10.3390/telecom6040100 · Cited by 15
How to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7
Metadata
- Authors
- Regev, O.
- Affiliations
- New York University (US)
- Corresponding author
- Regev, Oded
- ORCID
- Regev, Oded
- Venue
- Journal of the ACM
- Published
- 2025-01-24
- Volume
- 72
- Issue
- 1
- Pages
- 1-13
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W4405331036
- Cited by
- 42
- References
- 4
- Citations by year
- 2026: 12 · 2025: 18
- FWCI
- 6.07
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Journal of the ACM (publishedVersion)
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Funders
- Simons Investigator Award from the Simons Foundation
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- quantum factoring, integer factorization, quantum circuits, quantum algorithms, classical post-processing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
