This work presents a classical simulation framework for circuit components associated with the modular-exponentiation and order-finding stages of Shor’s factoring algorithm. The study examines five experimental cases and combines reversible state evolution, a dual-uint64 representation, Numba just-in-time execution, sparse grouping of phase amplitudes, and Fourier analysis. Its principal contribution is an occupancy-aware Fourier procedure that evaluates singleton groups analytically and applies the conventional fast Fourier transform only to groups containing multiple occupied phase positions. For the instance N = 4,028,033, this procedure reduced the number of FFT calls from 60,970 to 4,566 and decreased the measured Fourier-processing time from 197.68 seconds to 18.11 seconds, a reduction of 90.84%. All five selected cases satisfied the seven adopted validation criteria. The work concerns computational optimization of a classical simulation pipeline; it does not claim execution on quantum hardware, quantum computational advantage, or a new factoring algorithm. The experimental dataset supporting this study is publicly available through Harvard Dataverse: https://doi.org/10.7910/DVN/OOYKSC.
This work presents a classical simulation framework for circuit components associated with the modular-exponentiation and order-finding stages of Shor’s factoring algorithm. The study examines five experimental cases and combines reversible state evolution, a dual-uint64 representation, Numba just-in-time execution, sparse grouping of phase amplitudes, and Fourier analysis. Its principal contribution is an occupancy-aware Fourier procedure that evaluates singleton groups analytically and applies the conventional fast Fourier transform only to groups containing multiple occupied phase positions. For the instance N = 4,028,033, this procedure reduced the number of FFT calls from 60,970 to 4,566 and decreased the measured Fourier-processing time from 197.68 seconds to 18.11 seconds, a reduction of 90.84%. All five selected cases satisfied the seven adopted validation criteria. The work concerns computational optimization of a classical simulation pipeline; it does not claim execution on quantum hardware, quantum computational advantage, or a new factoring algorithm. The experimental dataset supporting this study is publicly available through Harvard Dataverse: https://doi.org/10.7910/DVN/OOYKSC.
A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.
Experimental realizations of Shor’s integer factorization algorithm on NISQ devices often rely on heavy circuit compilation that inadvertently encodes prior knowledge of the solution, bypassing the core challenge of quantum arithmetic. In this work, we present a hardware-execution baseline for the quantum order-finding routine where modular exponentiation is kept explicit as a sequence of controlled modular multiplications. We explicitly acknowledge that our approach relies on strong prior structural knowledge: the moduli are deliberately chosen as products of Fermat primes, and that ensures the multiplication constants ck=A2kmodN will reduce to identities or powers of two. However, unlike compiled demonstrations that hardcode the final state, this structural advantage is used strictly as an experimental proxy to make explicit arithmetic feasible on current hardware. Every non-trivial controlled modular multiplication is executed and verified by intermediate checkpoint measurements. We ran the resulting circuits on IBM superconducting devices for N∈{51,85,255,771} . For moduli up to N=255 , we observed Hellinger fidelities up to 0.946, while for N=771 we quantitatively characterize the signal degradation caused by increased circuit depth and accumulated hardware noise. By reporting logical and device-compiled resource counts, this methodology provides a reproducible reference point for studying depth-induced degradation in structured instances of order-finding and evaluating future hardware-aware optimizations.
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.
A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.
The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.