Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Innovative Mechanisms for Industry Applications

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

Published Oct 1, 2026• 0 citations
Publisher

Abstract

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

DOI
10.1109/icimia69818.2026.11744907

Related papers

Simulating Shor's Algorithm with QuantumRings and the Emerging Threats to RSA Encryption in the Quantum Era

Shafeeq Rahman Thottoli, Musfar Muhamed Kozhikkal

Quantum computing has raised significant concerns regarding the security of classical cryptographic systems, particularly RSA, as it depends on the computational difficulty of factoring large semiprime numbers.In this study, we demonstrate the practical application of Shor's algorithm by successfully factorizing a semiprime integer, up to 30 bits (857830637 = 29167 X 29411) using the QuantumRings simulator.Our work highlights the effectiveness of Shor's algorithm in solving the factorization problem in polynomial time, which will significantly improve over the classical method for a large number.The results suggest that with advances in quantum hardware, such as increasing qubit counts and improving error correction, breaking larger RSA keys (e.g., RSA-2048) may soon become feasible.This seriously threatens current cryptographic systems, emphasizing the need to adopt post-quantum cryptography.Our findings aim to raise awareness among researchers, policymakers, and industry leaders of the importance of preparing for a quantum-safe future.

International Journal of Science and Research (IJSR)•Apr 22, 2025•0 citations

Evaluating the Quantum Capabilities in Factorization RSA Modulus

Yaser Alkurdi, Qasem S. Abu Al-Haija

Quantum computing has emerged as a groundbreaking technology, revolutionizing the speed and capabilities of computation. Traditional computing, based on bits represented by 0s and 1s, has limitations in storage and computational efficiency, even with parallel processing. In contrast, quantum computing operates on qubits, enabling exponential reductions in storage requirements and faster computation via quantum parallelism. One prominent quantum algorithm, Shor's Algorithm, presents a significant threat to RSA encryption. This Algorithm efficiently factors large integers, a task considered intractable for classical computers. By leveraging classical and quantum computation techniques, Shor's Algorithm employs the Euclidean algorithm and the Quantum Fourier Transform (QFT) to find the greatest common divisor and perform period-finding, respectively. This research paper explores the implementation and implications of Shor's Algorithm in breaking RSA encryption. Through experiments conducted in IBM's Quantum Lab, the Algorithm successfully factorizes integers, showcasing its efficacy in practice. By examining the potential impact of quantum computing on RSA and exploring the capabilities of Shor's Algorithm, this research contributes to advancing the field of quantum computing and understanding its implications for modern cryptographic systems. The findings underscore the need for post-quantum cryptography to ensure secure communication and data protection in the era of quantum computing.

International Conference on Frontiers of Engineering and Emerging Technologies (FET)•Apr 22, 2026•0 citations

Experimental Analysis of Attacks on RSA & Rabin Cryptosystems using Quantum Shor’s Algorithm

Ritu Thombre, Babita Jajodia

In this world of massive communication networks, data security and confidentiality are of crucial importance for maintaining secured private communication and protecting information against eavesdropping attacks. Existing cryptosystems provide data security and confidentiality by the use of encryption and signature algorithms for secured communication. Classical computers use cryptographic algorithms that use the product of two large prime numbers for generating public and private keys. These classical algorithms are based on the fact that integer factorization is a non-deterministic polynomial-time (NP) problem and requires super-polynomial time making it impossible for large enough integers. Shor’s algorithm is a well-known algorithm for factoring large integers in polynomial time and takes only O(b3) time and O(b) space on b-bit number inputs. Shor’s algorithm poses a potential threat to the current security system with the ongoing advancements of Quantum computers. This paper discusses how Shor’s algorithm will be able to break integer factorization-based cryptographic algorithms, for example, Rivest–Shamir–Adleman (RSA) and Rabin Algorithms. As a proof of concept, experimental analysis of Quantum Shor’s algorithm on existing public-key cryptosystems using IBM Quantum Experience is performed for factorizing integers of moderate length (seven bits) due to limitations of thirty-two qubits in present IBM quantum computers. In a nutshell, this work will demonstrate how Shor’s algorithm poses threat to confidentiality and authentication services.

AIJR Proceedings•Jan 1, 2021•11 citations

The Impact of Quantum Noise on Shor's Algorithm and Its Cryptographic Applications

Wael M. F. Abdel-Rehim

Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.

•May 12, 2025•2 citations

Quantum Inspired Technique for Cracking RSA

Nitesh Kumar Rijwani, Brijesh Kumar Chaurasia

This paper explores a quantum-inspired technique for factoring semi-prime integers, a problem central to the security of RSA cryptography. While Shor's algorithm offers a polynomial-time solution on a quantum computer, posing a significant threat to RSA, current quantum hardware limitations hinder its practical implementation. This study simulates Shor's algorithm classically, replacing the quantum period-finding subroutine—the source of the quantum speedup—with a classical method to analyze its performance. The experiments factored semi-primes ranging from 2 to 8 digits, demonstrating that while the technique works, the execution time increases exponentially with the size of the number, escalating from seconds for small integers to an order of minutes for an 8-digit number. This highlights the inefficiency of classical period-finding compared to the quantum approach. The results validate the theoretical framework of Shor's algorithm but underscore the impracticality of classical simulations for cryptographic-scale integers. This work also explores the necessity of advancing quantum computing to realize scalable factorization while classical methods remain confined to pedagogical or small-scale applications. The study emphasizes the urgency of hybrid quantum-classical optimizations and reinforces Shor's algorithm as pivotal for future cryptographic vulnerability assessments and quantum-ready solutions.

International Conference on Information Systems and Computer Networks (ISCON)•Sep 5, 2025•2 citations

RSA Prime Factorization on IBM Qiskit

Matthew Evans Audric Rengkung, Arya Wicaksana

The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.

Journal of Internet Services and Information Security•May 30, 2023•10 citations
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
Quantum computing has raised significant concerns regarding the security of classical cryptographic systems, particularly RSA, as it depends on the computational difficulty of factoring large semiprime numbers.In this study, we demonstrate the practical application of Shor's algorithm by successfully factorizing a semiprime integer, up to 30 bits (857830637 = 29167 X 29411) using the QuantumRings simulator.Our work highlights the effectiveness of Shor's algorithm in solving the factorization problem in polynomial time, which will significantly improve over the classical method for a large number.The results suggest that with advances in quantum hardware, such as increasing qubit counts and improving error correction, breaking larger RSA keys (e.g., RSA-2048) may soon become feasible.This seriously threatens current cryptographic systems, emphasizing the need to adopt post-quantum cryptography.Our findings aim to raise awareness among researchers, policymakers, and industry leaders of the importance of preparing for a quantum-safe future.
Quantum computing has emerged as a groundbreaking technology, revolutionizing the speed and capabilities of computation. Traditional computing, based on bits represented by 0s and 1s, has limitations in storage and computational efficiency, even with parallel processing. In contrast, quantum computing operates on qubits, enabling exponential reductions in storage requirements and faster computation via quantum parallelism. One prominent quantum algorithm, Shor's Algorithm, presents a significant threat to RSA encryption. This Algorithm efficiently factors large integers, a task considered intractable for classical computers. By leveraging classical and quantum computation techniques, Shor's Algorithm employs the Euclidean algorithm and the Quantum Fourier Transform (QFT) to find the greatest common divisor and perform period-finding, respectively. This research paper explores the implementation and implications of Shor's Algorithm in breaking RSA encryption. Through experiments conducted in IBM's Quantum Lab, the Algorithm successfully factorizes integers, showcasing its efficacy in practice. By examining the potential impact of quantum computing on RSA and exploring the capabilities of Shor's Algorithm, this research contributes to advancing the field of quantum computing and understanding its implications for modern cryptographic systems. The findings underscore the need for post-quantum cryptography to ensure secure communication and data protection in the era of quantum computing.
In this world of massive communication networks, data security and confidentiality are of crucial importance for maintaining secured private communication and protecting information against eavesdropping attacks. Existing cryptosystems provide data security and confidentiality by the use of encryption and signature algorithms for secured communication. Classical computers use cryptographic algorithms that use the product of two large prime numbers for generating public and private keys. These classical algorithms are based on the fact that integer factorization is a non-deterministic polynomial-time (NP) problem and requires super-polynomial time making it impossible for large enough integers. Shor’s algorithm is a well-known algorithm for factoring large integers in polynomial time and takes only O(b3) time and O(b) space on b-bit number inputs. Shor’s algorithm poses a potential threat to the current security system with the ongoing advancements of Quantum computers. This paper discusses how Shor’s algorithm will be able to break integer factorization-based cryptographic algorithms, for example, Rivest–Shamir–Adleman (RSA) and Rabin Algorithms. As a proof of concept, experimental analysis of Quantum Shor’s algorithm on existing public-key cryptosystems using IBM Quantum Experience is performed for factorizing integers of moderate length (seven bits) due to limitations of thirty-two qubits in present IBM quantum computers. In a nutshell, this work will demonstrate how Shor’s algorithm poses threat to confidentiality and authentication services.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
This paper explores a quantum-inspired technique for factoring semi-prime integers, a problem central to the security of RSA cryptography. While Shor's algorithm offers a polynomial-time solution on a quantum computer, posing a significant threat to RSA, current quantum hardware limitations hinder its practical implementation. This study simulates Shor's algorithm classically, replacing the quantum period-finding subroutine—the source of the quantum speedup—with a classical method to analyze its performance. The experiments factored semi-primes ranging from 2 to 8 digits, demonstrating that while the technique works, the execution time increases exponentially with the size of the number, escalating from seconds for small integers to an order of minutes for an 8-digit number. This highlights the inefficiency of classical period-finding compared to the quantum approach. The results validate the theoretical framework of Shor's algorithm but underscore the impracticality of classical simulations for cryptographic-scale integers. This work also explores the necessity of advancing quantum computing to realize scalable factorization while classical methods remain confined to pedagogical or small-scale applications. The study emphasizes the urgency of hybrid quantum-classical optimizations and reinforces Shor's algorithm as pivotal for future cryptographic vulnerability assessments and quantum-ready solutions.
The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.