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.
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 advent of quantum computing poses a fundamental threat to classical cryptographic systems, particularly RSA encryption, which relies on the computational limit of prime factorization. This paper presents a comparative analysis of four integer factorization approaches-a selfcurated brute-force classical implementation, optimized Trial Division, Pollard's Rho algorithm, and Shor's algorithmevaluated across a dataset of increasing semiprime inputs representative of scaled-down RSA encryption keys. Through Python-based implementations and simulations, we empirically measure and plot runtime complexity for classical methods while modeling theoretical runtimes for Shor's algorithm, given hardware limitations. Our findings reveal the exponential scaling limitations of classical algorithms, and contrast them with the polynomial-time behavior of Shor's algorithm. Despite being simulated, Shor's consistently flatter runtime trendline demonstrated its theoretical superiority and the critical urgency of post-quantum cryptography. This study not only visualizes the performance divide between classical and quantum paradigms but also underscores the transformational potential of quantum computing in modern cryptanalysis.
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.
The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.
Cryptography is crucial for protecting private information. However, the emergence of quantum computing poses a significant threat to the security of classical cryptographic systems. Traditional algorithms such as RSA can be vulnerable to quantum attacks. Shor's quantum algorithm can break RSA encryption in polynomial time. This article examines the RSA cryptosystem, the impact of quantum computing on cryptography, the challenges of quantum computing, and its applications in various fields. The article also presents an experiment comparing traditional and Shor factorization methods for semi-prime numbers. Although the experiment does not involve factoring extremely large numbers, it demonstrates the simplicity of implementing algorithms. By conducting experiments and analysing the results, computer science students can better understand the principles of quantum computing, its capabilities, and limitations, and develop practical skills.
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 dissertation analyzes the impact of quantum computing on the security of classical cryptographic systems, with a focus on the vulnerability of the RSA algorithm. RSA cryptography is based on the difficulty of factoring large prime numbers, a task considered computationally very difficulty for classical computers. However, with quantum computing, especially through Shor’s algorithm—this barrier can be overcome. Shor’s algorithm allows factorization in polynomial time, which would completely compromise the security of RSA.The dissertation presents the theoretical foundations of both cryptography and quantum computing, explaining key concepts such as qubits, superposition, entanglement, and quantum parallelism. It details the operation of Shor’s algorithm, from identifying the period of the modular exponential function to applying the Quantum Fourier Transform (QFT) and phase estimation to obtain the prime factors of a composite number.In addition to the theoretical component, the work includes practical implementations of the algorithm in both classical and simulated quantum environments, using IBM’s Qiskit library. Finally, it discusses post-quantum cryptography as a secure alternative in light of technological advancements, highlighting methods based on lattices, codes, hash functions, and multivariate systems.The conclusion emphasizes the urgency of adopting cryptographic systems resistant to quantum computing, as ongoing advances increasingly make the breaking of RSA a realistic threat. Post-quantum cryptography is mentioned as a necessary response to the challenge posed by quantum computing.In conclusion, although current quantum computers do not yet have sufficient power to break RSA in practice, technological progress is steadily bringing that scenario closer. Therefore, it is essential to develop and adopt quantum-resistant cryptographic systems to ensure information security in the coming decades.