A Comparative Analysis of Shor’s Algorithm and Factorization Methods
DOI:
https://doi.org/10.22401/ANJS.29.2.13Keywords:
Shor’s algorithm, Factorization methods, Quantum computing, SecurityAbstract
Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC), Fermat's Factorization, and the Quadratic Sieve (QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper also discusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm.
References
[1] Iqbal, S. S.; Zafar, A.; "Enhanced Shor’s algorithm with quantum circuit optimization". Int. J. Inf. Technol., 16 (4): 2725–2731, 2024.
[2] Willsch, D.; Willsch, M.; Jin, F.; De Raedt, H.; Michielsen, K.; "Large-Scale Simulation of Shor’s Quantum Factoring Algorithm". Mathematics, 11 (19): 4222, 2023.
[3] Pavlenko, V.; Hlukhov, V.; "Quantum-inspired computing: comparsion of variants of Shor’s algorithm". Adv. Cyber-Physical Syst., 10 (1): 71–76, 2025.
[4] Bastos, D. C.; Brasil Kowada, L. A.; "How to detect whether Shor’s algorithm succeeds against large integers without a quantum computer". Procedia Comput. Sci., 195: 145–151, 2021.
[5] Abdulwahhab, S. A.; Hussien, Q. M.; Taha, I. F.; "New Design of NTRU Key Using QKD Variants". in AIP Conference Proceedings 3009: 030007, 2024.
[6] Alaa Abdulwahhab, S.; Mohammed Hussein, Q.; Fakhri Al-Shaikhli, I.; "An overview of number theory research unit variant development security". Indones. J. Electr. Eng. Comput. Sci., 28 (2): 1164, 2022.
[7] Cai, J.-Y.; "Shor’s algorithm does not factor large integers in the presence of noise". Sci. China Inf. Sci., 67 (7): 173501, 2024.
[8] Buchanan, W.; Woodward, A.; "Will quantum computers be the end of public key encryption?". J. Cyber Secur. Technol., 1 (1): 1–22, 2017.
[9] "An overview of Quantum Cryptography and Shor’s Algorithm". Int. J. Adv. Trends Comput. Sci. Eng., 9 (5): 7487–7495, 2020.
[10] Wong, H. Y.; "Shor’s Algorithm". in Introduction to Quantum Computing 289–298, Springer International Publishing:, Cham, 2024.
[11] Kumar, M.; Mondal, B.; "Study on Implementation of Shor’s Factorization Algorithm on Quantum Computer". SN Comput. Sci., 5 (4): 413, 2024.
[12] Muruganantham, B.; Shamili, P.; Kumar, S. G.; Murugan, A.; "Quantum cryptography for secured communication networks". Int. J. Electr. Comput. Eng., 10 (1): 407, 2020.
[13] Hamdi, S. M.; Zuhori, S. T.; Mahmud, F.; Pal, B.; "A Compare between Shor’s quantum factoring algorithm and General Number Field Sieve". in 2014 International Conference on Electrical Engineering and Information & Communication Technology 1–6, IEEE:, 2014.
[14] Larasati, H. T.; Kim, H.; "Quantum cryptanalysis landscape of shor’s algorithm for elliptic curve discrete logarithm problem". in International Conference on Information Security Applications 91–104, Springer:, 2021.
[15] Jia, S.; "Comparison of Performances for Quantum and Conventional Algorithms: Shor’s algorithm and Boson Sampling". Highlights Sci. Eng. Technol., 38: 493–501, 2023.
[16] Varshney, S.; Charpe, P.; Padmavathy, R.; Pal, S. K.; "Relation collection using Pollard special-q sieving to solve integer factorization and discrete logarithm problem". J. Supercomput., 77 (3): 2734–2769, 2021.
[17] Ali, F.; Mustafa, M.; "IMMFV2: Improved Modified Fermat Factorization Algorithm". in International Conference on Engineering Software for Modern Challenges 114–122, Springer:, 2021.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Alaa Khudhair Abbas, Saba Hussein Rashid, Saba Alaa Abdulwahab, Imad Fakhri Al-Shaikhli
This work is licensed under a Creative Commons Attribution 4.0 International License.
.jpg)
