How Shor's Algorithm Turns Factoring into Period Finding

Every public-key primitive deployed on the internet rests on a problem believed to be hard for classical computers: integer factorisation for RSA, discrete logarithms in a multiplicative group for finite-field Diffie-Hellman, discrete logarithms in an elliptic curve group for ECDH and ECDSA. Shor’s algorithm solves all three in polynomial time on a sufficiently large quantum computer, given one subroutine that quantum hardware performs natively: period finding by Fourier transform. The consequence is not that cryptography stops working. It is that the hardness argument underpinning three specific families of schemes evaporates, while symmetric primitives keep roughly half of their security.

The reduction: from factoring to finding a period

The first step of the algorithm is classical. Suppose $N$ is the RSA modulus, a product of two secret primes. Pick a random $a$ coprime to $N$ and consider the function

$$f(x) = a^x \bmod N.$$

Because the multiplicative group modulo $N$ is finite, this sequence is eventually periodic with some period $r$, meaning $a^r \equiv 1 \pmod{N}$ and $r$ is the smallest such exponent. The order $r$ is the object the quantum part of the algorithm computes. Once it is known, classical arithmetic extracts the factors: if $r$ is even and $a^{r/2} \not\equiv -1 \pmod N$, then $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$ are non-trivial divisors of $N$. A random $a$ fails these conditions with probability at most about one half, so a handful of repetitions suffice. The whole difficulty therefore sits in computing the multiplicative order of a random element.

Two details in the reduction matter for anyone evaluating the threat. First, the failures are detectable: an attempt either produces a factor or reveals that the order was unhelpful, so the algorithm never silently returns a wrong key. Second, the reduction works unchanged if $N$ is replaced by any group where exponentiation is efficiently computable, which is why the same structure breaks Diffie-Hellman over a prime field and, in a variant known as the discrete logarithm version, over an elliptic curve. The elliptic curve case is actually easier for the attacker per bit of classical security, because the known classical attack on generic elliptic curve discrete logarithms is generic square-root time rather than sub-exponential index calculus. Schemes that survive are those whose underlying problem has no known algebraic structure of this kind.

Quantum phase estimation on the exponentiation circuit

The quantum computer is given the unitary operator $U_a$ that maps $|y\rangle$ to $|ay \bmod N\rangle$. Its eigenstates are the states

$$|u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \omega^{-sk} |a^k \bmod N\rangle, \qquad \omega = e^{2\pi i / r},$$

and the eigenvalue attached to $|u_s\rangle$ is $\omega^s$. Knowing the eigenvalue gives $s/r$, and continued-fraction expansion of that rational recovers $r$. The algorithm does not construct these eigenstates, which would require knowing $r$ in advance. It uses the standard phase-estimation trick instead: prepare the uniform superposition of all $x$ over a large register, apply $U_a$ a controlled number of times so the phase is kicked back onto the input register, and then take an inverse quantum Fourier transform.

Concretely, the input register holds $t$ qubits and the output register holds enough qubits to represent values below $N$. After the controlled multiplications, the input register is in a superposition whose amplitudes, written as a function of the register value, are periodic with period $r$, up to the phase kickback. The inverse Fourier transform converts that periodicity into peaks at multiples of $2^t/r$. Measurement returns one such peak with high probability, and the rational reconstruction step recovers $r$ exactly when $t$ is large enough that the peak spacing resolves the period. Shor’s analysis gives $t$ of order $2\log_2 N$ qubits as sufficient, so an RSA-2048 modulus needs roughly 4096 qubits in the input register alone. Implementations that precompute $a^{2^i} \bmod N$ for each bit position reduce the multiplier depth but not the total qubit count.

One serious subtlety: the phase-estimation return value is a good approximation to $s/r$ only if the phase is exactly a multiple of $2^{-t}$ on the Fourier grid, which it generally is not. The analysis handles this by showing that for most values of $s$ the measured integer is within a small distance of $2^t s / r$, and the continued fraction of that measured integer still has $r$ as a convergent when $r$ is below $2^{t/2}$. This is why the input register must be larger than the output register; the extra qubits buy precision in the rational reconstruction.

What the circuit cost implies about the migration timeline

The dominant cost is not the Fourier transform, which needs a quadratic number of gates in the register size but is otherwise simple, nor the modular arithmetic of the controlled multiplications, which in the naive construction requires $O(\log^3 N)$ gates per exponentiation. The dominant engineering obstacle is fault tolerance. Phase estimation has to run for a number of error-corrected time steps proportional to the size of the computation, and each logical qubit is encoded across many physical qubits to keep the logical error rate low enough that the algorithm does not fail. Published resource estimates for RSA-2048 factoring land in the range of thousands of logical qubits and tens of millions of physical qubits when the error correction overhead at realistic physical error rates is included. That figure, not the abstract algorithmic complexity, is what makes “harvest now, decrypt later” the operative risk model: an adversary recording traffic today can wait a decade for the hardware, so any data with a confidentiality lifetime beyond the arrival of the machine is already exposed.

The same analysis decides which schemes need immediate replacement. Symmetric ciphers and hash functions are not broken structurally. Grover’s search gives a quadratic speedup against exhaustive key search, which is a constant-factor reduction in the effective security level rather than a polynomial one. Doubling the key size restores the margin: AES-256 remains at roughly 128 bits of security against a quantum adversary, and SHA-256 stays around 128 bits against preimage search, while collision resistance falls to roughly 85 bits by the birthday bound applied to the square-root speedup. NIST’s post-quantum guidance therefore targets only key establishment and digital signatures for replacement, and the replacement primitives are specified in FIPS 203 for key encapsulation and FIPS 204 and 205 for signatures. What those schemes depend on, and why the quantum algorithm has nothing to attack, is the subject of the rest of the cluster, starting with the Learning With Errors problem that underpins the lattice family.

The classical pre-processing that survives

Shor’s algorithm does not eliminate classical effort; it relocates it. Before the quantum part runs, the algorithm chooses $a$, computes the modular exponentiation table $a^{2^i} \bmod N$ for each bit position of the input register, and after measurement runs a continued-fraction expansion on a rational approximation. The table construction is already a non-trivial classical computation for a 2048-bit modulus: it requires $2t \approx 4096$ modular multiplications by a full-size constant, each of which costs $O(b^2)$ word operations for a $b$-bit modulus in schoolbook arithmetic, or less with Montgomery multiplication and a fast multiplier.

The measurement outcomes are probabilistic, and the rational reconstruction can fail in two ways. The continued fraction may return a denominator that is not the order, or the order may be odd, or $a^{r/2} \equiv -1$. Each of these is detected and the algorithm restarts. The expected number of repetitions is small, on the order of a handful, because the failure conditions are each bounded away from one. For the discrete logarithm version applied to an elliptic curve group, the structure changes: the group operation is point addition rather than modular multiplication, and the “exponentiation table” becomes a table of scalar multiples of the generator or of the target point, depending on the variant. The quantum circuit is size-comparable to the factoring circuit at the same bit size, and the classical pre-processing is cheaper because elliptic curve point addition is cheaper than 2048-bit modular multiplication. That asymmetry is why the elliptic curve schemes are considered more exposed per unit of classical security than RSA at a large modulus.

Why the reduction does not transfer to lattice problems

Shor’s algorithm requires an efficiently computable group with an abelian structure that admits a Fourier transform over a hidden subgroup. Integer factoring and discrete logarithms are precisely hidden-subgroup problems over abelian groups. Lattice problems such as Learning With Errors ask for the closest vector in a lattice or for a short vector, which are not hidden-subgroup problems, and no quantum algorithm is known that solves them better than the best classical one by more than polynomial factors. The same applies to decoding a random linear code, which is what McEliece signatures rely on. This is a negative statement about what is currently known, not a proof of security: nobody has shown that a quantum computer cannot attack lattices. But the structural barrier is real, and it is the reason the replacement schemes were designed against classical hardness assumptions believed to hold against both kinds of adversary.