Fast versions of Shor's quantum factoring algorithm
Open accessAbstract
We present fast and highly parallelized versions of Shor's algorithm. With a sizable quantum computer it would then be possible to factor numbers with millions of digits. The main algorithm presented here uses FFT-based fast integer multiplication. The quick reader can just read the introduction and the ``Results'' section.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Fault-tolerant quantum computation
Shor, P. W. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 943 · see citing works
Monroe, C. R., & Bollinger, J. J. (1997) · Physics World · doi:10.1088/2058-7058/10/3/22 · Cited by 12 · see citing works
Flagged first, then by citations
Research works printed but not linked: 5
- [1][1] J.I. Cirac and P. Zoller Quantum Computations with Cold Trapped Ions Physical Review Letters, Volume 74, Number 200 (May 1995), page 4091
- [2][2] J. I. Cirac et al., 'Quantum state transfer and entanglement distribution among distant nodes in a quantum network', quant-ph/9611017 · arXiv
- [5][5] P. Shor, Fault-Tolerant Quantum Computation. in 37th Symposium on Foundations of Computing, IEEE Computer Society Press, 1996, pp. 56-65 quant-ph/9605011 · arXiv
- [6][6] E. Knill, R. Laflamme and W. Zurek, Accuracy Threshold for Quantum Computation , quant-ph/9610011 · arXiv
- [7][7] D. Aharonov, M. Ben-Or, Fault-Tolerant Quantum Computation With Constant Error quant-ph/9611025 · arXiv
Cited by
Sorted by citations
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · see citing works
“Number of Sequential Total computational Toffoli Toffoli References logical qubits gates gates 2N 40N(3) 40N(3) [35–37] 5N 600N(2) O(N(3) logN) [38] 2N(2) 15N log(2)N O(N(3) log(2)N) [39] O(N(3)) O(log(3)N) O(N(3) log(3)N) [40]”
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 · see citing works
Shor's discrete logarithm quantum algorithm for elliptic curves
Proos, J., & Zalka, C. (2003) · Quantum Information and Computation · doi:10.26421/qic3.4-3 · Cited by 367 · see citing works
Self-citationDobšíček, M., Johansson, G., Shumeiko, V., & Wendin, G. (2007) · Physical Review A · doi:10.1103/physreva.76.030306 · Cited by 208 · see citing works
Circuit for Shor's algorithm using 2n+3 qubits
Beauregard, S. (2003) · Quantum Information and Computation · doi:10.26421/qic3.2-8 · Cited by 206 · see citing works
Addition on a Quantum ComputerPreprint
Draper, T. G. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0008033 · Cited by 196 · see citing works
Fast quantum modular exponentiation
Van Meter, R., & Itoh, K. M. (2005) · Physical Review A · doi:10.1103/physreva.71.052320 · Cited by 181 · see citing works
Bernstein, D. J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12929-2_6 · Cited by 142 · see citing works
Gidney, C., & Fowler, A. G. (2019) · Quantum · doi:10.22331/q-2019-04-30-135 · Cited by 152 · see citing works
Implementation of Shor's algorithm on a linear nearest neighbour qubit array
Fowler, A. G., Devitt, S. J., & Hollenberg, L. C. L. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011827.2011828 · Cited by 139 · see citing works
Quantum addition circuits and unbounded fan-out
Takahashi, Y., Tani, S., & Kunihiro, N. (2010) · Quantum Information and Computation · doi:10.26421/qic10.9-10-12 · Cited by 136 · see citing works
Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures
Bocharov, A., Roetteler, M., & Svore, K. M. (2017) · Physical Review A · doi:10.1103/physreva.96.012306 · Cited by 112 · see citing works
Bernstein, D. J., Heninger, N., Lou, P., & Valenta, L. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59879-6_18 · Cited by 103 · see citing works
Architectural implications of quantum computing technologies
Meter, R. V., & Oskin, M. (2006) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/1126257.1126259 · Cited by 92 · see citing works
Requirements for fault-tolerant factoring on an atom-optics quantum computer
Devitt, S. J., Stephens, A. M., Munro, W. J., & Nemoto, K. (2013) · Nature Communications · doi:10.1038/ncomms3524 · Cited by 78 · see citing works
Introduction to Quantum AlgorithmsPreprint
Shor, P. W. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0005003 · Cited by 81 · see citing works
Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?
Bernstein, D. J. (2009) · TU/e Research Portal · Cited by 61 · see citing works
Arithmetic on a Distributed-Memory Quantum Multicomputer
Van Meter, R., Munro, W. J., Nemoto, K., & Itoh, K. M. (2006) · CERN Document Server (European Organization for Nuclear Research) · Cited by 58 · see citing works
Introduction to quantum algorithms
Shor, P. W. (2002) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/058/1922896 · Cited by 55 · see citing works
A novel quantum evolutionary algorithm and its application
Yang, S., Wang, M., & Jiao, L. (2004) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2004.1330945 · Cited by 48 · see citing works
Shor's algorithm on a nearest-neighbor machine
Kutin, S. A. (2006) · arXiv · doi:10.48550/arxiv.quant-ph/0609001 · Cited by 47 · see citing works
A quantum circuit for Shor's factoring algorithm using 2n+2 qubits
Takahashi, Y., & Kunihiro, N. (2006) · Quantum Information and Computation · doi:10.26421/qic6.2-4 · Cited by 47 · see citing works
A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth
Pham, P., & Svore, K. (2012) · Quantum information & computation · doi:10.26421/qic13.11-12-3 · Cited by 69 · see citing works
Fast quantum modular exponentiation architecture for Shor's factoring alogrithm
Pavlidis, A., & Gizopoulos, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.7-8-8 · Cited by 38 · see citing works
Quantum Division Circuit Based on Restoring Division Algorithm
Khosropour, A., Aghababa, H., & Forouzandeh, B. (2011) · International Conference on Information Technology: New Generations · doi:10.1109/itng.2011.177 · Cited by 35 · see citing works
Bio‐Inspired and Nanoscale Integrated Computing
Eshaghian‐Wilner, M. M., & service), W. I. (. (2009) · Wiley eBooks · doi:10.1002/9780470429983 · Cited by 34 · see citing works
Entanglement and its role in Shor's algorithm
Kendon, V. M., & Munro, W. J. (2006) · Quantum Information and Computation · doi:10.26421/qic6.7-6 · Cited by 31 · see citing works
NISQ Quantum Computing: A Security-Centric Tutorial and Survey [Feature]
Chen, F., Jiang, L., Müller, H. A., Richerme, P., Chu, C., Fu, Z., & Min, Y. (2024) · IEEE Circuits and Systems Magazine · doi:10.1109/mcas.2024.3349665 · Cited by 27 · see citing works
Using Fewer Qubits in Shor’s Factorization Algorithm via Simultaneous Diophantine Approximation
Seifert, J. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45353-9_24 · Cited by 25 · see citing works
Factoring 51 and 85 with 8 qubits
Geller, M. R., & Zhou, Z. (2013) · Scientific Reports · doi:10.1038/srep03023 · Cited by 25 · see citing works
Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
Wang, X., Zhang, Y.-C., Li, Z., Xu, B., Yu, S., & Guo, H. (2017) · Quantum Information and Computation · doi:10.26421/qic17.13-14 · Cited by 22 · see citing works
Simulations of Shor’s algorithm using matrix product states
Wang, D. S., Hill, C. D., & Hollenberg, L. C. L. (2017) · Quantum Information Processing · doi:10.1007/s11128-017-1587-x · Cited by 22 · see citing works
Reversible Karatsuba's Algorithm
Kowada, L. A. B., Portugal, R., & de Figueiredo, C. M. H. (2006) · doi:10.3217/jucs-012-05-0499 · Cited by 19 · see citing works
Circuit for Shor's algorithm using 2n+3 qubitsPreprint
Beauregard, S. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0205095 · Cited by 18 · see citing works
Quantum Plain and Carry Look-Ahead AddersPreprint
Cheng, K.-W., & Tseng, C. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0206028 · Cited by 17 · see citing works
A Faster Half Subtractor Circuit Using Reversible Quantum Gates
Orts, F. J., Ortega, G., & Garzón, E. M. (2019) · Baltic Journal of Modern Computing · doi:10.22364/bjmc.2019.7.1.08 · Cited by 16 · see citing works
Classical Control of Large-Scale Quantum Computers
Devitt, S. J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08494-7_3 · Cited by 14 · see citing works
Oonishi, K., Tanaka, T., Uno, S., Satoh, T., Meter, R. V., & Kunihiro, N. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3136195 · Cited by 17 · see citing works
Towards Large-Scale Quantum ComputationPreprint
Fowler, A. G. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0506126 · Cited by 13 · see citing works
Batterman, R. W. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197568613.003.0006 · Cited by 14 · see citing works
Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation
Reif, J. H. (1998) · Lecture notes in computer science · doi:10.1007/978-3-540-49382-2_10 · Cited by 12 · see citing works
Quantum Algorithms: Overviews, Foundations, and Speedups
Wang, S. P., & Sakk, E. (2021) · International Conference on Cryptography, Security and Privacy (CSP) · doi:10.1109/csp51677.2021.9357505 · Cited by 12 · see citing works
A public key cryptosystem based on data complexity under quantum environment
Wu, W., Zhang, H., Wang, H., Mao, S., Jia, J., & Liu, J. (2015) · Science China Information Sciences · doi:10.1007/s11432-015-5408-5 · Cited by 12 · see citing works
Speeding up implementation for Shor’s factorization quantum algorithm
Fu, X.-Q., Bao, W., & Zhou, C. H. (2010) · Chinese Science Bulletin · doi:10.1007/s11434-010-3039-1 · Cited by 11 · see citing works
Gidney, C. (2019) · arXiv · doi:10.48550/arxiv.1905.07682 · Cited by 11 · see citing works
A Faster Half Subtractor Circuit Using Reversible Quantum Gates
Orts, F. J., Ortega, G., & Garzón, E. M. (2019) · Baltic Journal of Modern Computing · doi:10.22364/bjmc.2018.7.1.08 · Cited by 8 · see citing works
Cryptography Based on Error Correcting Codes
Repka, M., & Cayrel, P.-L. (2014) · Advances in information security, privacy, and ethics book series · doi:10.4018/978-1-4666-5808-0.ch005 · Cited by 7 · see citing works
An n-bit general implementation of Shor's quantum period-finding algorithm
Davies, J. T. A., Rickerd, C. J., Grimes, M. A., & Güney, D. Ö. (2016) · Quantum Information and Computation · doi:10.26421/qic16.7-8-6 · Cited by 7 · see citing works
Feasibility Analysis of Cracking RSA with Improved Quantum Circuits of the Shor’s Algorithm
Liu, X., Yang, H., & Yang, L. (2021) · Security and Communication Networks · doi:10.1155/2023/2963110 · Cited by 8 · see citing works
A 2D Nearest-Neighbor Quantum Architecture for FactoringPreprint
Pham, P., & Svore, K. M. (2012) · arXiv (Cornell University) · Cited by 6 · see citing works
How to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7 · see citing works
Concrete Quantum Cryptanalysis of Binary Elliptic Curves via Addition Chain
Taguchi, R., & Takayasu, A. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30872-7_3 · Cited by 5 · see citing works
Yan, S. Y. (2018) · Springer eBooks · doi:10.1007/978-3-319-72536-9_5 · Cited by 6 · see citing works
Efficient and exact quantum compression
Reif, J. H., & Chakraborty, S. (2007) · Information and Computation · doi:10.1016/j.ic.2007.01.005 · Cited by 5 · see citing works
Quantum Computational Number Theory
Yan, S. Y. (2012) · Wiley eBooks · doi:10.1002/9781118188606.ch10 · Cited by 5 · see citing works
Matrix Product Operator Simulations of Quantum Algorithms
Woolfe, K. J. (2015) · Minerva Access (University of Melbourne) · Cited by 6 · see citing works
Multi-update Mode Quantum Evolutionary Algorithm for a combinatorial problem
Xin, W., & Shigeru, F. (2010) · International Conference on Computer and Automation Engineering · doi:10.1109/iccae.2010.5451502 · Cited by 4 · see citing works
A quantum primality test with order finding
Vela, A. D., & García-Escartín, J. C. (2018) · Quantum Information and Computation · doi:10.26421/qic18.13-14-5 · Cited by 4 · see citing works
Techniques for Quantum Computing
Kaye, P. (2007) · UWSpace (University of Waterloo) · Cited by 4 · see citing works
t-bit semiclassical quantum Fourier transform
Fu, X.-Q., Bao, W., Zhou, C. H., & Song, Z. (2012) · Chinese Science Bulletin · doi:10.1007/s11434-011-4692-8 · Cited by 3 · see citing works
Approximate encoded permutations and piecewise quantum adders
Gidney, C. (2019) · arXiv · doi:10.48550/arxiv.1905.08488 · Cited by 3 · see citing works
Q-Gen: A Parameterized Quantum Circuit Generator
Mao, Y., Shresthamali, S., & Kondo, M. (2025) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2025.3572142 · Cited by 2 · see citing works
Concrete quantum cryptanalysis of binary elliptic curves via addition chain
Taguchi, R., & Takayasu, A. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04323-y · Cited by 2 · see citing works
Design and Implementation of Quantum Factorization Algorithm
Fu, X.-Q., Bao, W., & Zhou, C. H. (2010) · International Symposium on Intelligent Information Technology and Security Informatics · doi:10.1109/iitsi.2010.150 · Cited by 2 · see citing works
New Approachs to Quantum Computer Simulaton in a Classical SupercomputerPreprint
Burger, J. R. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0308158 · Cited by 2 · see citing works
Quantum Attacks on ECDLP-Based Cryptosystems
Yan, S. Y. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7722-9_4 · Cited by 1 · see citing works
Implementation of the Rainbow signature scheme on SoC FPGA
Přeučil, T., Socha, P., & Novotný, M. (2022) · Euromicro Conference on Digital System Design (DSD) · doi:10.1109/dsd57027.2022.00074 · Cited by 1 · see citing works
周, 淳., 付, 向., 鲍, 皖., & 宋, 震. (2011) · Chinese Science Bulletin (Chinese Version) · doi:10.1360/csb2011-56-26-2250 · Cited by 1 · see citing works
Low-depth quantum architectures for factoring
Harrow, A. W., & Pham, P. (2013)
Quantum information engineering: concepts to quantum technologies
Devitt, S. J. (2007) · Minerva Access (University of Melbourne)
Quantum Algorithms for Integer Factorization
Yan, S. Y. (2015) · Springer eBooks · doi:10.1007/978-3-319-25823-2_3
QUANTUM MODELS AND MODES OF COMPUTATION AND COMMUNICATION
Gruska, J., & Fasanengarten, A. (2000)
Classical Control of Large-Scale Quantum ComputersPreprint
Devitt, S. J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.4943
A quantum algorithm for computing the Carmichael functionPreprint
García-Escartín, J. C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.02488
Reif, J. H. (2009) · Wiley eBooks · doi:10.1002/9780470429983.ch3
Imre, S., & Balázs, F. (2004) · Wiley eBooks · doi:10.1002/9780470869048.refs
Baradziej, S. (2026) · Frontiers in Computer Science · doi:10.3389/fcomp.2026.1914634
- Authors
- Zalka, C.
- Affiliations
- Los Alamos National Laboratory (US)
- Corresponding author
- Zalka, Christof
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 1998
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- quant-ph/9806084
- OpenAlex
- W2593569272
- Cited by
- 73
- References
- 5
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 2 · 2023: 2 · 2022: 1 · 2021: 4 · 2019: 4 · 2018: 2 · 2017: 4 · 2016: 1 · 2015: 3 · 2014: 4 · 2013: 5 · 2012: 4
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Japan Society for the Promotion of Science (19K20267)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- Shor's algorithm, quantum computing
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
