Implementation And Analysis of Regev’s Quantum Factorization Algorithm
References
- R. L. Rivest, A. Shamir and L. Adleman (1978). “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, no. 2.
- P. W. Shor (1994). “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science.
- P. W. Shor (1999). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Review, vol. 41, no. 2, 1999.
- D. Dziechciarz and M. Niemiec (2025). “Efficiency analysis of NIST-standardized post-quantum cryptographic algorithms for digital signatures in various environments,” Electronics, vol. 14, no. 1.
- R. Dhaulakhandi, B. K. Behera and F. J. Seo (2024). “Factorization of large tetra and penta prime numbers on IBM quantum processor,” APL Quantum, vol. 1, p. 026113, 06.
- P. M. Mutter and G. Burkard (2023). “Theory of qubit noise characterization using the long-time cavity transmission,” Physical Review A, vol. 107, no. 2.
- O. Regev (2025). “An efficient quantum factoring algorithm,” J. ACM, vol. 72.
- M. Kiebert (2024). “Oded Regev’s quantum factoring algorithm.” Mathematics and Computer Science at Informatics Institute, Korteweg-de Vries Institute for Mathematics, Faculty of Sciences, University of Amsterdam.
- S. Ragavan and V. Vaikuntanathan (2024). “Space-efficient and noise-robust quantum factoring,” in Advances in Cryptology – CRYPTO 2024 (L. Reyzin and D. Stebila, eds.), (Cham), pp. 107–140, Springer Nature Switzerland.
- M. Ekerå and J. Gärtner (2025). “A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography,” IACR Communications in Cryptology, vol. 2, no. 1.
- B. Stępień (2021). “Algorytm Shora dla IBM Qiskit,” Master’s thesis, AGH University of Krakow, Krakow, Poland. [in Polish].
- S. Beauregard (2003). “Circuit for Shor’s algorithm using 2n + 3 qubits,” arXiv preprint quant-ph/0205095.
- Y. Takahashi (2008). E?icient quantum circuits for arithmetic operations and their applications. PhD thesis, The University of Electro-Communications, Tokyo.
- T. Häner, M. Roetteler and K. M. Svore (2017). “Factoring using 2n + 2 qubits with Toffoli based modular multiplication.” URL: https://arxiv.org/abs/1611.07995.
- Y. Takahashi and N. Kunihiro (2006). “A quantum circuit for Shor’s factoring algorithm using 2n + 2 qubits,” Quantum Information & Computation, vol. 6, no. 2.
- X. Tan and P. Gao (2024). “An efficient quantum circuit implementation of Shor’s algorithm for GPU accelerated simulation,” AIP Advances, vol. 14, no. 2.
- R. Cleve and J. Watrous (2000). “Fast parallel circuits for the quantum Fourier transform,” in Proc. 41st Annual Symposium on Foundations of Computer Science.
- D. Harvey and J. Van Der Hoeven (2021). “Integer multiplication in time O (n log n),” Annals of Mathematics, vol. 193, no. 2.
- C. Gidney (2019). “Asymptotically efficient quantum Karatsuba multiplication,” arXiv preprint arXiv:1904.07356.
- G. D. Kahanamoku-Meyer and N. Y. Yao (2024). “Fast quantum integer multiplication with zero ancillas,” arXiv preprint arXiv:2403.18006.
- C. Zalka (2006). “Shor’s algorithm with fewer (pure) qubits,” arXiv preprint quant-ph/0601097.
- C. Gidney (2017). “Factoring with n + 2 clean qubits and n – 1 dirty qubits,” arXiv preprint arXiv:1706.07884.
- M. Roetteler, M. Naehrig, K. M. Svore and K. Lauter (2017). “Quantum resource estimates for computing elliptic curve discrete logarithms,” in Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security.
- A. Lenstra, H. Lenstra and L. László (1982). “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261.
- C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del R’ıo, M. Wiebe, P. Peterson, P. G’erard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke and T. E. Oliphant (2020). “Array programming with NumPy,” Nature, vol. 585.
- A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson and J. M. Gambetta (2024). “Quantum computing with Qiskit.” arXiv 10.48550/arXiv.2405.08810.
- Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean and T. E. O’Brien (2023). “Quantum error mitigation,” Reviews of Modern Physics, vol. 95, no. 4.
- IBM (2024). “Error mitigation and suppression techniques.” URL: https://quantum.cloud.ibm.com/docs/en/guides/error-mitigation-and-suppression-techniques, Accessed on March 17, 2026.
- O. Regev (2024). “An efficient quantum factoring algorithm quantum colloquium.” URL: https://simons.berkeley.edu/events/efficient-quantum-factoring-algorithm-quantum-colloquium.
Language: English
Page range: 230 - 252
Submitted on: Nov 20, 2025
Accepted on: Mar 10, 2026
Published on: Jun 4, 2026
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Related subjects:
© 2026 Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, Piotr Chołda, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.