The Cruicality of Shor's Algorithm In Breaking RSA Encryption

Vaishnavi Khandu Purkar, Roshani Sunil Gavande, Shailaja Satishrao Kulkarni +1 more

Jun-Ya Wang, Xui-Chengn Chang, Hung-Ju Wang

In quantum algorithm, the Shor's algorithm can find prime decomposition of very big numbers easily and break RSA encryption much faster and more efficiently than in the classical case. How to complicant the public key to slow down the speed and efficiency of Shor's algorithm to secure our RSA encryption scheme is main issue in this study. By using classical random simulation to operation as quantum bits to complicate the RSA cryptosystem, even Shor's algorithm can not to find prime decomposition of very big numbers n with qubits random simulation easily.

Pooya Farshim, Benoît Libert, Kenneth G. Paterson +1 more

Alice Flarend, Robert Hilborn

Abstract This chapter sets the background for the famous Shor algorithm that can allow a sufficiently powerful quantum computer to easily break the current classical RSA encryption method. The RSA algorithm relies on the impossibility of even the most powerful classical computers to factor large numbers in any practical length of time. Before going through the details of the RSA encryption method, the number theory of the modulus or mod function is explained with many examples including exponential ones. The connection between factoring and the periodicity of mod functions is emphasized because it is needed for the RSA and Shor algorithms. The in-depth explanation of the RSA algorithm makes use of number theory to explain how the encryption key can be made public while other information is kept secret to ensure secure communication.

Bartosz Przydatek

Arnav Jain

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.