Shor's algorithm: complexity, RSA and what is still unproved

Definition

Shor's algorithm is a randomized quantum algorithm for factoring integers and for computing discrete logarithms. The 1994 conference paper introduced the method. The 1997 paper in SIAM Journal on Computing is the account this library quotes for the bound. Both papers work in the quantum gate-array model: a uniform family of quantum circuits, with a small allowed probability of error.

The problems are the ones Shor names as the basis of proposed cryptosystems. Factoring an integer, and finding discrete logarithms in the multiplicative group modulo a prime, are not given classical polynomial-time algorithms in that paper. Shor gives polynomial-time quantum algorithms for both.

Intuition

Factoring reduces to order-finding, and that reduction is classical. Pick a random integer a that is coprime to the number n you want to factor. The order r of a modulo n is the smallest positive integer such that a^r is congruent to 1 modulo n. When r is even, and a^(r/2) is not congruent to −1 modulo n, the greatest common divisors of n with a^(r/2) ± 1 are nontrivial factors. If the test fails, try another base.

The quantum routine finds r. It prepares a superposition over exponents, writes a^x mod n into a second register with a reversible circuit, and applies a quantum Fourier transform to the exponent register. Measuring that register yields a value close to a multiple of 1/r. Continued fractions, on a classical computer, recover a candidate for r. Shor identifies modular exponentiation as the bottleneck. The Fourier transform is not where the time goes.

The two registers become entangled by the modular-exponentiation circuit. The interference that makes the samples useful happens only if that entanglement is preserved until the measurement.

Complexity

This is a gate-complexity statement, not an oracle query bound. Compare Grover's algorithm if the question is query complexity.

In the 1997 paper, the factoring algorithm takes asymptotically O((log n)^2 (log log n) (log log log n)) steps on a quantum computer, together with classical post-processing polynomial in log n. Here n is the integer being factored, so log n tracks the number of bits of the input. The shape of the bound comes from reversible modular exponentiation. With the Schönhage–Strassen multiplication algorithm, exponentiation of l-bit numbers costs O(l^2 log l log log l) gates, which is the same shape once l is about log n.

The procedure is randomized. Shor shows that a run finds the order on at least a constant-over-log-log-r fraction of trials, so O(log log r) repetitions succeed with high probability. He also describes extra classical checks, attributed there to arguments of Odlyzko and of Knill, that can bring the expected number of quantum trials down toward a constant. The post-processing is not an exponential classical search in disguise.

The same paper computes discrete logarithms in the multiplicative group modulo a prime, with two modular exponentiations and two Fourier transforms. That is the discrete logarithm this page means, unless it says otherwise. Quantum phase estimation, in Kitaev's formulation, is a later and now standard way to present the same period-finding idea. The 1997 paper's own subroutine is the quantum Fourier transform, written out for a power-of-two modulus. The phase-estimation page is where the precision bound and the eigenstate assumption are stated.

Applications and limits

RSA is the factoring case people mean. Diffie–Hellman in a multiplicative group modulo a prime is the discrete-logarithm case in the 1997 paper. Elliptic-curve groups are a later adaptation: Proos and Zalka show how to carry the discrete-logarithm algorithm over to elliptic curves defined over a prime field. This page does not repeat their qubit counts. Those counts predate the error-correction overhead in later resource estimates, and quoting them beside a 2048-bit RSA figure would mix two different models.

Gidney and Ekerå estimate the cost of factoring 2048-bit RSA integers under explicit assumptions: a planar grid of noisy superconducting qubits, nearest-neighbor connectivity, a physical gate error rate of 10^−3, a surface-code cycle of 1 microsecond, and a reaction time of 10 microseconds. Under those assumptions they estimate about 20 million noisy qubits and about 8 hours. In the abstract circuit model, ignoring distillation, routing, and error correction, they give a leading cost of about 3n logical qubits and about 0.3 n^3 Toffoli gates for an n-bit RSA integer, with lower-order terms stated in the paper. Read those figures as the output of that cost model.

Gidney (2025) revises that estimate. The preprint, arXiv:2505.15917, says a 2048-bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. It states the same physical assumptions as the 2019 arXiv version of the Gidney and Ekerå estimate: a square grid of qubits with nearest-neighbor connections, a uniform gate error rate of 0.1 percent, a surface-code cycle of 1 microsecond, and a control-system reaction time of 10 microseconds. The preprint attributes the qubit reduction mainly to approximate residue arithmetic, yoked surface codes, and magic-state cultivation, and the longer runtime mainly to more Toffoli gates and fewer magic-state factories. Those are the paper's own attributions. Both the 2021 figure and the 2025 figure are outputs of a cost model under stated assumptions. Neither is a machine that has factored a 2048-bit integer.

Shor already treats imprecision and decoherence as the obstacle to running a long circuit. A fault-tolerant machine is the setting in which the polynomial bound becomes an engineering budget rather than a counting argument. Cai and Young (2026) analyze a relative-noise model on the small controlled rotations inside the quantum Fourier transform, and they prove a threshold at which the expected polynomial runtime fails for a positive-density set of primes. The model and the cutoff are in the digest of 12 Oct 2026. Symmetric cryptography is a different algorithm. Grover's quadratic search does not factor integers, and Shor's algorithm does not exhaust a symmetric key.

Reading the source

Start with the abstract and with sections 2 and 5 of the 1997 paper: the gate array, then factoring. Section 6 is the discrete logarithm. Section 7 is the practicality discussion, including precision and decoherence. The 1994 FOCS paper is the preliminary version. Use Gidney and Ekerå (2021) and Gidney (2025) together when the question is the size of a fault-tolerant attack under stated physical assumptions: the 2025 preprint is the later estimate, and it does not erase the 2021 figure. Use Proos and Zalka when the question is elliptic curves.