IEEE Access

A Step-by-Step Shor’s Algorithm Walkthrough: From Theory to Implementation

Trung Nguyen, Samuel Petruescu, Shrikant S. Jadhav, Hiu Yung Wong

Published Jan 1, 2026• 0 citations

Abstract

Quantum computing is inherently abstract and often counterintuitive from the perspective of classical physics. For learners to develop a deeper understanding, it is useful to study a practical example thoroughly, from its mathematical formalism to quantum circuit implementation. Shor's algorithm for period finding, which can then be used for prime factorization, is demonstrated in this paper due to its practical significance. While numerous publications on Shor's algorithm exist, they tend to focus on advanced theoretical analysis, specific implementation details, or narrowly defined research aspects; consequently, they are often not well-suited for educational purposes for beginning and intermediate learners. This paper presents a rigorous step-by-step walkthrough of Shor's algorithm, utilizing the conventional approach, and discusses the construction of the quantum oracle with illustrative numerical examples. This is followed by classical simulations and implementations on actual quantum hardware. The aim is to allow learners with minimal mathematical background to follow and understand the algorithm. Through this process, the paper also attempts to interpret and connect the key underlying quantum computing concepts of superposition, entanglement, interference, quantum oracle, and phase kick-back that are often assumed to be trivial and omitted in research papers, yet are particularly challenging for novice learners to internalize. In the numerical examples, reduced-qubit cases are included. By contrasting the results from the reduced-qubit configurations with the standard ones, learners can better appreciate the key enablers in Shor's algorithm and how the accuracy decreases with a smaller number of qubits. Moreover, reduced-qubit examples (e.g., 5 qubits) are small enough to be implemented in a hardware emulator, such as a low-cost and low-capacity Field Programmable Gate Array (FPGA), which can be used in experimental hardware classes for students to understand how to use an FPGA to simulate quantum circuits.

DOI: 10.1109/access.2026.3716184

Related papers

Deconstructing Shor’s Algorithm Using Quantum Fourier Transform

Dushyant Kumar, Balwinder Raj, Gurmohan Singh

Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.

Indian Journal of Pure & Applied PhysicsJan 1, 20260 citations

Implementing Shor’s algorithm in a quantum computing simulation environment for educational purposes

Syed Muhammad Muneeb Ali, Monika Wolfmayr

This article presents a detailed implementation of Shor’s quantum factoring algorithm, which served as the cornerstone for a pilot project at Jamk University of Applied Sciences. The primary goal was to leverage this significant algorithm to establish and validate a reusable quantum simulation environment on a high-performance computing (HPC) platform. We report the successful factorization of the integer 15, executed on the Finnish CSC’s MAHTI supercomputer using a 9-qubit quantum circuit developed in the Qiskit framework. This work provides a comprehensive overview of the principles behind Shor’s algorithm and a methodical breakdown of its simulation. Furthermore, it documents the practical software challenges faced during the environment’s configuration, focusing on library versioning and dependencies. The purpose of this work is to provide a systematic introduction to implement Shor’s algorithm at computer science or applied mathematics classes in institutions of higher education such as universities of applied sciences. The successful factorization provides an initial validation of the simulation workflow for this benchmark case, while the detailed account of implementing Shor’s algorithm offers a practical guide and valuable insights for future quantum computing initiatives at educational institutions with a focus on computer science or scientific computing.

Discover EducationAug 6, 20260 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 eBooksNov 14, 20250 citations

Near term implementation of Shor's Algorithm using Qiskit

Casimer M. DeCusatis, Emily Mcgettrick

Although the fundamental principles of quantum computing have been known for decades, it is only within the past few years that practical quantum computers have become available. Since these systems are limited to a small number of qubits, they cannot demonstrate quantum advantage for many practical problems. Accordingly, there has been an effort to develop near term implementations of algorithms purely for research and education. In this paper, we discuss a near term implementation of Shor's Algorithm using the Qiskit language on an IBM Q System One quantum computer. We extend currently available documentation by providing a full circuit diagram for Shor's Algorithm including gates specific to the implementation using Qiskit. We present an implementation capable of factoring small two-digit prime numbers, and discuss the limitations of noise when using real quantum computers vs. simulations.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)Jan 27, 20216 citations

Performance Evaluation of Shor Algorithm on Simulated Quantum Hardware with Circuit Level Analysis

T. Thamaraimanalan, Anandakumar Haldorai, Arulmurugan Ramu +1 more

Shor’s algorithm stands as a breakthrough in quantum computing due to its potential to factor large integers exponentially quicker than classical algorithms. However, implementing and evaluating this algorithm on real quantum computer hardware remains exciting due to qubit limitations, gate noise, and hardware constraints. This research presents a comprehensive performance evaluation of Shor’s algorithm using simulated quantum backends provided by Qiskit. A flexible and generic implementation is proposed, allowing dynamic input of integers to be factored, with randomized co-prime selection and automated circuit generation. The algorithm is tested on various semiprime numbers, such as 15, 21, and 35, using IBM’s Aer simulator. A major contribution of this work is the circuit-level analysis conducted both before and after transpilation. Metrics such as gate counts, circuit depth, and simulator runtime are extracted to assess scalability and resource requirements. High-resolution plots of the pre-transpiled circuits are saved to visualize algorithmic complexity, while post-transpilation metrics inform future quantum hardware feasibility. The output measurement distributions are analyzed to estimate periodicity and derive correct factors. The proposed implementation is compared with existing fixed-instance Shor demonstrations to highlight its flexibility and extensibility. Experimental results show consistent success in factor retrieval and provide valuable insight into circuit growth and complexity under realistic constraints. This analysis lays the groundwork for future adaptation to NISQ hardware and contributes to understanding Shor’s algorithm from both computational and architectural perspectives.

Journal of Machine and ComputingJul 2, 20253 citations

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

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.

arXiv:2306.09122QuantaSep 15, 20238 citations