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

Oxford University Press eBooks

RSA Encryption and the Shor Factoring Algorithm

Alice Flarend, Bob Hilborn

Published Apr 15, 2022• 0 citations
Publisher

Abstract

Abstract This chapter is the most formidable in the book, but it provides a deep and complete understanding of the classic Shor factoring algorithm. Alice and Bob set the context for the algorithm by explaining how the difficulty of factoring large numbers plays a critical role in securing encrypted communications channels, using RSA encryption as an example. The Shor algorithm, if implemented on a sufficiently large quantum computer, could defeat those encryption schemes by finding those factors relatively quickly, a task that would take years or more on even the fastest classical supercomputers. Alice and Bob lead us through some number theory to establish the connection between factoring and finding the period of a periodic function. They then show how the clever use of quantum algorithms—this is Shor’s main contribution—leads to a fast way to find the required period using quantum Fourier transforms.

DOI
10.1093/oso/9780192857972.003.0013

Related papers

RSA Encryption and Number Theory

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.

Oxford University Press eBooks•Jul 9, 2026•0 citations

Shor Factoring Algorithm and the Quantum Fourier Transform

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

Oxford University Press eBooks•Jul 9, 2026•0 citations

Shor's Algorithm: Factoring and Cryptanalysis

Bhupendra Singh, Mohankumar Mylsamy, Thamaraimanalan Thangarajan

“Shor's Algorithm: Factoring and Cryptanalysis” focuses on Shor's Algorithm, particularly its application to factoring and cryptanalysis. It begins with an overview of Shor's algorithm, detailing the classical extraction of periods from measured values and the quantum gates required for the Quantum Fourier Transform (QFT). Further, this chapter explores the applications and limitations of Shor's algorithm, including its impact on RSA encryption. A literature review follows, discussing Shor's algorithm in the context of quantum computation, its effectiveness on RSA, and the effects of imperfections on its factorization process. The section also includes an experimental study of Shor's algorithm using IBM Q, followed by a practical implementation of factoring numbers N=21 and N=35. Further, it covers resource estimation, quantum simulations, and different types of simulators in IBM Qiskit, including state vector, QASM, Matrix Product State (MPS), and stabilizer simulators, providing insights into their use cases and the limits of classical simulation.

CRC Press eBooks•Nov 14, 2025•0 citations

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

E. Gerjuoy

The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•101 citations

Breaking RSA with Quantum Computing

Blaz Bacnik

We take a look at RSA encryption algorithm and what makes it secure. Some consideration is given to its current use, showing that it plays an important role in ensuring privacy on the Internet. A way of factoring large numbers with Shor’s factorization algorithm is given, as well as a shortcut to directly breaking RSA. Next, we present basics of some of the implementations, their drawbacks and make an estimation of how long will our RSA keys remain safe.

•Jan 1, 2008•2 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
Abstract This chapter is the most formidable in the book, but it provides a deep and complete understanding of the classic Shor factoring algorithm. Alice and Bob set the context for the algorithm by explaining how the difficulty of factoring large numbers plays a critical role in securing encrypted communications channels, using RSA encryption as an example. The Shor algorithm, if implemented on a sufficiently large quantum computer, could defeat those encryption schemes by finding those factors relatively quickly, a task that would take years or more on even the fastest classical supercomputers. Alice and Bob lead us through some number theory to establish the connection between factoring and finding the period of a periodic function. They then show how the clever use of quantum algorithms—this is Shor’s main contribution—leads to a fast way to find the required period using quantum Fourier transforms.
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.
Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.
“Shor's Algorithm: Factoring and Cryptanalysis” focuses on Shor's Algorithm, particularly its application to factoring and cryptanalysis. It begins with an overview of Shor's algorithm, detailing the classical extraction of periods from measured values and the quantum gates required for the Quantum Fourier Transform (QFT). Further, this chapter explores the applications and limitations of Shor's algorithm, including its impact on RSA encryption. A literature review follows, discussing Shor's algorithm in the context of quantum computation, its effectiveness on RSA, and the effects of imperfections on its factorization process. The section also includes an experimental study of Shor's algorithm using IBM Q, followed by a practical implementation of factoring numbers N=21 and N=35. Further, it covers resource estimation, quantum simulations, and different types of simulators in IBM Qiskit, including state vector, QASM, Matrix Product State (MPS), and stabilizer simulators, providing insights into their use cases and the limits of classical simulation.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
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.