Why It Beats Classical Factoring

This module has built Shor's algorithm layer by layer. Now it is time to step back and ask the central question: exactly how much faster is it? The gap between Shor's algorithm and the best classical factoring methods is not a modest improvement — it is an exponential chasm, and understanding why requires a careful comparison of the two computational models.

The classical benchmark: the General Number Field Sieve

The fastest known classical algorithm for factoring an integer $N$ is the General Number Field Sieve (GNFS). Its heuristic running time on a machine performing one operation per clock cycle is

$T_{\text{GNFS}}(N) = \exp\!\left(c \cdot (\ln N)^{1/3} (\ln \ln N)^{2/3}\right),$

where $c \approx 1.923$ is a small constant. This is sub-exponential in $\ln N$ but still grows much faster than any polynomial in $\ln N$ . In computational complexity language it is written $L_N[1/3, c]$ using the $L$ -notation for sub-exponential algorithms.

To make the scaling concrete, let $n = \lfloor \log_2 N \rfloor$ be the bit length of $N$ (the natural input size). Then $\ln N \approx n \ln 2$ , so

$T_{\text{GNFS}} = \exp\!\left(c'\, n^{1/3} (\ln n)^{2/3}\right), \qquad c' = c\,(\ln 2)^{1/3}.$

This is a function that grows faster than any polynomial in $n$ but slower than $2^n$ . Doubling $n$ multiplies the cost by $\exp(c' \cdot 2^{1/3} n^{1/3} (\ln n)^{2/3}) / \exp(c' n^{1/3} (\ln n)^{2/3})$ , a very large factor.

Shor's algorithm: polynomial in the bit length

Shor's quantum algorithm for factoring $N$ runs in time

$T_{\text{Shor}}(N) = O\!\left((\log N)^3\right) = O\!\left(n^3\right)$

elementary quantum gate operations, where the $O(n^3)$ cost comes almost entirely from the modular-exponentiation subroutine $U_f$ , which requires $O(n^2)$ controlled modular multiplications each costing $O(n)$ gates. The inverse Quantum Fourier Transform adds $O(n^2)$ gates, which is dominated by the $O(n^3)$ cost of $U_f$ . The initial Hadamard layer and measurement add only $O(n)$ steps.

The algorithm must be repeated a small constant number of times to boost the probability that the classical post-processing step (continued fractions plus GCD) successfully extracts the factors. The expected number of repetitions is $O(\log \log N) = O(\log n)$ , so the total cost is

$T_{\text{Shor}} = O\!\left(n^3 \log n\right).$

This is polynomial in $n$ , placing integer factoring in the complexity class $\mathbf{BQP}$ (bounded-error quantum polynomial time).

The exponential gap

The ratio of the two running times illustrates how large the advantage is:

$\frac{T_{\text{GNFS}}}{T_{\text{Shor}}} = \frac{\exp\!\left(c' n^{1/3}(\ln n)^{2/3}\right)}{O(n^3 \log n)}.$

As $n \to \infty$ , the numerator grows super-polynomially while the denominator is polynomial, so the ratio diverges. In formal terms, for every polynomial $p(n)$ there exists $n_0$ such that for all $n \geq n_0$ ,

$T_{\text{GNFS}}(n) > p(n) \cdot T_{\text{Shor}}(n).$

This is what computer scientists mean by an exponential speedup: the quantum algorithm achieves a speedup larger than any fixed polynomial.

For concrete numbers, consider RSA-2048 ( $n = 2048$ ):

GNFS estimate: $\approx 2^{117}$ operations (infeasible with all classical hardware ever built).
Shor estimate: $\approx 2048^3 \approx 8.6 \times 10^9$ quantum gate operations per repetition (feasible for a large fault-tolerant quantum computer after error correction overhead is included, though the physical qubit count in that regime is in the millions).

Why the QFT creates the speedup

The heart of the speedup is the Quantum Fourier Transform's ability to detect the period $r$ of the function $f(x) = a^x \bmod N$ using only $O(n^2)$ gates, whereas the best classical algorithm for period-finding costs at least $O(\sqrt{r}) \geq O(\sqrt{N})$ steps (by a birthday-paradox lower bound).

Classically, to find the period $r$ of a function, you must evaluate it enough times to notice a repetition. By the birthday paradox, you need $\Omega(\sqrt{r})$ evaluations before a collision is likely. Since $r$ can be as large as $\lambda(N) \approx N / 2$ (the Carmichael function), this is at least $\Omega(\sqrt{N}) = 2^{n/2}$ evaluations — exponential in $n$ .

Quantumly, the period-finding subroutine prepares a superposition of all $2^n$ inputs simultaneously in a single pass, then applies the inverse QFT to concentrate the measurement probability on integer multiples of $2^n / r$ . A single measurement (plus continued-fraction extraction) reveals $r$ with $\Omega(1 / \log r)$ probability. No classical evaluation-and-wait strategy can replicate this: the QFT exploits the interference between $2^n$ amplitudes to perform, in effect, a global Fourier analysis in $O(n^2)$ steps. Classical fast Fourier transforms require $O(2^n \cdot n)$ operations because they must process all $2^n$ function values explicitly.

Scaling behavior: a table

The table below shows estimated raw gate counts (ignoring constants) for several bit lengths $n$ , comparing GNFS against the quantum gate count for Shor's algorithm before fault-tolerance overhead.

| Bit length $n$ | GNFS cost (approx.) | Shor gate count ( $n^3$ ) | |:-:|:-:|:-:| | 128 | $2^{34}$ | $2.1 \times 10^6$ | | 512 | $2^{64}$ | $1.3 \times 10^8$ | | 1024 | $2^{87}$ | $1.1 \times 10^9$ | | 2048 | $2^{117}$ | $8.6 \times 10^9$ |

The GNFS column uses the standard estimate $2^{c(n \ln 2)^{1/3}(\ln(n \ln 2))^{2/3}}$ with $c = 1.923$ . Even ignoring error-correction overhead, the asymptotic advantage of the quantum algorithm is unmistakable.

Implications for cryptography

RSA key lengths have grown over time to stay ahead of classical advances in GNFS. 1024-bit RSA was deprecated around 2013 and 2048-bit RSA is the current standard. But longer keys only delay the problem: because the GNFS cost is sub-exponential, doubling the key length provides a large but eventually exhausted buffer. Shor's algorithm eliminates the buffer entirely — for any fixed key length, a sufficiently powerful quantum computer can factor $N$ in polynomial time.

This is why the cryptographic community is transitioning to post-quantum cryptography: schemes based on lattice problems, hash functions, and other mathematical structures for which no quantum speedup comparable to Shor's is known. The transition is underway at standards bodies including NIST (which finalized its first post-quantum standards in 2024), driven directly by the complexity analysis covered in this lesson.

Summary

| Property | GNFS (classical) | Shor's algorithm (quantum) | |:--|:-:|:-:| | Time complexity | $L_N[1/3, 1.923]$ (sub-exponential) | $O(n^3 \log n)$ (polynomial) | | Scales as key doubles | cost increases by factor $\exp(\Theta(n^{1/3}))$ | cost increases by factor $\approx 8$ | | Key insight | Algebraic number sieves | QFT detects periodicity via interference | | Threat to RSA-2048 | No practical threat today | Decisive threat on fault-tolerant hardware |

The exponential speedup from polynomial-time quantum period-finding over sub-exponential classical sieving is the engine behind every cryptographic concern about large-scale quantum computers. It is also one of the most striking demonstrations of the power of quantum interference — and a complete proof that $\mathbf{BQP}$ is not contained in $\mathbf{BPP}$ would resolve one of the deepest open questions in computational complexity theory.