Quantum Information & Computation
Volume 26
RESEARCH ARTICLE Open access

Implementation And Analysis of Regev’s Quantum Factorization Algorithm

Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, Piotr Chołda

Author affiliations
  • Przemysław Pawlitko1
  • Natalia Moćko1
  • Marcin Niemiec1
  • Piotr Chołda1
  1. AGH University of Krakow, Institute of Telecommunications and Cybersecurity, Mickiewicza 30, Krakow, Poland

pp. 230-252 · 10.2478/qic-2026-0012

Read PDF View on Reference Global
On this page

Abstract

Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.
Open accessCC BY-NC-ND 4.0

Keywords

  • factorization
  • quantum algorithms
  • quantum computers
  • Regev’s algorithm
  • Shor’s algorithm

Suggested citation

Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, Piotr Chołda (2026). Implementation And Analysis of Regev’s Quantum Factorization Algorithm. Quantum Information & Computation, 26(1), 230-252. https://doi.org/10.2478/qic-2026-0012

Download BibTeX

References (29)

  1. 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.DOI: 10.1145/359340.359342Google Scholar
  2. P. W. Shor (1994). “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science.Google Scholar
  3. P. W. Shor (1999). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Review, vol. 41, no. 2, 1999.DOI: 10.1137/S0036144598347011Google Scholar
  4. 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.DOI: 10.3390/electronics14010070Google Scholar
  5. 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.DOI: 10.1063/5.0194993Google Scholar
  6. 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.DOI: 10.1103/PhysRevA.107.022601Google Scholar
  7. O. Regev (2025). “An efficient quantum factoring algorithm,” J. ACM, vol. 72.DOI: 10.1145/3708471Google Scholar
  8. 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.Google Scholar
  9. 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.DOI: 10.1007/978-3-031-68391-6_4Google Scholar
  10. 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.DOI: 10.62056/ayzojb0krGoogle Scholar
  11. B. Stępień (2021). “Algorytm Shora dla IBM Qiskit,” Master’s thesis, AGH University of Krakow, Krakow, Poland. [in Polish].Google Scholar
  12. S. Beauregard (2003). “Circuit for Shor’s algorithm using 2n + 3 qubits,” arXiv preprint quant-ph/0205095.DOI: 10.26421/QIC3.2-8Google Scholar
  13. Y. Takahashi (2008). E?icient quantum circuits for arithmetic operations and their applications. PhD thesis, The University of Electro-Communications, Tokyo.Google Scholar
  14. 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.DOI: 10.26421/QIC17.7-8-7Google Scholar
  15. 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.DOI: 10.26421/QIC6.2-4Google Scholar
  16. 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.DOI: 10.1063/5.0186385Google Scholar
  17. R. Cleve and J. Watrous (2000). “Fast parallel circuits for the quantum Fourier transform,” in Proc. 41st Annual Symposium on Foundations of Computer Science.DOI: 10.1109/SFCS.2000.892140Google Scholar
  18. D. Harvey and J. Van Der Hoeven (2021). “Integer multiplication in time O (n log n),” Annals of Mathematics, vol. 193, no. 2.DOI: 10.4007/annals.2021.193.2.4Google Scholar
  19. C. Gidney (2019). “Asymptotically efficient quantum Karatsuba multiplication,” arXiv preprint arXiv:1904.07356.Google Scholar
  20. G. D. Kahanamoku-Meyer and N. Y. Yao (2024). “Fast quantum integer multiplication with zero ancillas,” arXiv preprint arXiv:2403.18006.Google Scholar
  21. C. Zalka (2006). “Shor’s algorithm with fewer (pure) qubits,” arXiv preprint quant-ph/0601097.Google Scholar
  22. C. Gidney (2017). “Factoring with n + 2 clean qubits and n – 1 dirty qubits,” arXiv preprint arXiv:1706.07884.Google Scholar
  23. 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.DOI: 10.1007/978-3-319-70697-9_9Google Scholar
  24. A. Lenstra, H. Lenstra and L. László (1982). “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261.DOI: 10.1007/BF01457454Google Scholar
  25. 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.DOI: 10.1038/s41586-020-2649-2Google Scholar
  26. 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.Google Scholar
  27. 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.DOI: 10.1103/RevModPhys.95.045005Google Scholar
  28. 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.Google Scholar
  29. O. Regev (2024). “An efficient quantum factoring algorithm quantum colloquium.” URL: https://simons.berkeley.edu/events/efficient-quantum-factoring-algorithm-quantum-colloquium.DOI: 10.1145/3708471Google Scholar