“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.
“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.
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.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.
Quantum Shor’s algorithm offers an exponential speedup over classical methods for integer factorization, a central problem to modern cryptography, and the implica- tions of Shor’s algorithm in factoring large numbers. The algorithm leverages on quantum parallelism to compute the period of a modular exponentiation function, employ- ing the Inverse Quantum Fourier Transform (IQFT) to extract periodicity, and classical post-processing to derive the factors. This final report of the Quantum Engineer- ing post-graduate course of the Fundacio Polit ́ enica de ` Catalunya, presents the main findings encountered in the implementation and benchmarking of Schor’s algorithm in real IBM quantum computers. To accomplish this, we created a command line tool made in Python, that allows the integration of the circuits implementing the Shor’s algorithm with the overall set of configuration parameters needed to perform the benchmark. In this report, we first provide an overview of the quantum factoring problem, followed by a detailed description of Shor’s algorithm, and its implementation using the Qiskit Python library. The circuit depth and noise effects are analyzed across different backend types, also different values for the optimization level and approximation degrees are configured when performing the circuit transpilation. As mentioned earlier different backend types were utilized for performance comparison, namely backend class with or without a noise model (AerSim), a fake backend class provided by the Qiskit library (fake provider), and the real quantum hardware (IBM Quantum Processing Units in January- June 2025).The study follows by analyzing the different error mitigation techniques: dynamic decoupling, Pauli twirling, the SABRE Optimization (Stochastic Algorithm for Quantum Boolean Optimization and Routing), and any combination of them. Once the optimum configuration is found, the maximum number that can be reasonably factorized with success is explored. Finally, the main conclusions, findings, and possible future research lines are presented, including the factorization of a N ≈ 1000 if appropriate parameters of the algorithm are selected.
Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.
To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.