Quantum Computing Algorithms for Integer Factorization: A Comparative Analysis

Authors

  • Dr. Nadia Ahmed Parul University, Ahemdabad

DOI:

https://doi.org/10.36676/mdmp.v1.i1.02

Keywords:

Quantum computing, Shor's algorithm, Integer factorization, Computational complexity, Comparative analysis

Abstract

The field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.

References

Shor, P. W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th Annual Symposium on Foundations of Computer Science, 124–134.

Nielsen, M. A., & Chuang, I. L. (2010). "Quantum Computation and Quantum Information: 10th Anniversary Edition." Cambridge University Press.

Bernstein, D. J., & Lange, T. (2017). "Post-quantum cryptography." Nature, 549(7671), 188-194.

Rivest, R. L., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 21(2), 120-126.

Boneh, D., & Shoup, V. (2000). "A Graduate Course in Applied Cryptography." http://crypto.stanford.edu/~dabo/cryptobook/.

Ekert, A., & Jozsa, R. (1996). "Quantum computation and Shor's factoring algorithm." Reviews of Modern Physics, 68(3), 733–753.

Childs, A. M., & Van Dam, W. (2010). "Quantum algorithms for algebraic problems." Reviews of Modern Physics, 82(1), 1–52.

Gheorghiu, A., & Mosca, M. (2019). "Factoring as a Service: A Survey on Factoring Algorithms, Cost Models and Hardness Amplification." arXiv preprint arXiv:1908.04212.

Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search." Proceedings, 28th Annual ACM Symposium on the Theory of Computing, 212-219.

Mosca, M., & Ekert, A. (1999). "The hidden subgroup problem and eigenvalue estimation on a quantum computer." Proceedings, 1st NASA International Conference on Quantum Computing and Quantum Communications, 174–188.

Downloads

Published

25-05-2024

How to Cite

Dr. Nadia Ahmed. (2024). Quantum Computing Algorithms for Integer Factorization: A Comparative Analysis. Modern Dynamics: Mathematical Progressions, 1(1), 6–9. https://doi.org/10.36676/mdmp.v1.i1.02

Issue

Section

Original Research Articles

Similar Articles

1 2 > >> 

You may also start an advanced similarity search for this article.