Shor's Algorithm, Structurally: Period-Finding and the Quantum Fourier Transform

The sentence "a quantum computer breaks RSA" hides a surprisingly compact idea. Peter Shor's 1997 result is not a brute-force search sped up; it is an exact reduction that turns factoring an integer into detecting the period of a periodic function, and then uses one quantum primitive — the Quantum Fourier Transform — to read that period off in a single shot. Everything cryptographically alarming about it follows from three moves that can be written on a page. Understanding those moves matters, because they tell you exactly what an adversary needs (a fault-tolerant machine of a certain size) and what they do not (any new mathematics). This article rebuilds the algorithm structurally, so the threat can be reasoned about rather than merely feared.

The reduction: factoring is order-finding in disguise

Fix an odd composite integer N that we wish to factor. Choose a base a with 1 < a < N. If gcd(a, N) is already greater than 1 we have stumbled onto a factor and are done, so assume gcd(a, N) = 1, meaning a is a unit modulo N. The multiplicative order of a modulo N is the smallest positive integer r such that a raised to the power r is congruent to 1 modulo N. This r is the period of the function that maps an exponent x to a raised to the power x, reduced modulo N — the function repeats every r steps.

The classical fact that makes factoring reducible to order-finding is elementary. Suppose r is even and a raised to the power r-over-2 is not congruent to minus one modulo N. Then a raised to the power r minus one factors as the product of a raised to the r-over-2 plus one and a raised to the r-over-2 minus one, and that product is a multiple of N while neither factor is. Consequently the greatest common divisor of a raised to the r-over-2 plus or minus one with N is a nontrivial factor of N, computable in polynomial time by Euclid's algorithm. A short number-theoretic argument shows that for a randomly chosen a the two lucky conditions — r even and the non-trivial square root — both hold with probability at least one half, so a handful of random bases suffice.

Every step here except finding r is classical and cheap. The entire quantum contribution of Shor's algorithm is a subroutine that computes the order r. That is the whole game: reduce a hard-looking problem to period-finding, then find the period quantumly.

The Quantum Fourier Transform, defined

The one genuinely quantum ingredient is the Quantum Fourier Transform, abbreviated Q F T. On a register of Q basis states labelled 0 through Q minus 1, where Q is a power of two, the Q F T is the linear map that sends a basis state x to an equally weighted superposition of all basis states y, each carrying a phase that rotates in proportion to the product x times y. It is the discrete Fourier transform of classical signal processing, but applied to quantum amplitudes rather than to a stored array — which is exactly why it is fast.

The reason the Q F T is central is that the discrete Fourier transform concentrates the amplitude of a periodic input onto the frequencies that match its period. If a register holds a uniform superposition over exponents that share a hidden period r, applying the Q F T produces large amplitudes precisely at the multiples of Q divided by r. A measurement then returns, with high probability, an integer close to some multiple of Q over r. The period, hidden in the structure of a superposition, becomes a number you can read.

Crucially, the Q F T on n qubits is implemented with on the order of n squared elementary gates — Hadamard gates and controlled phase rotations — whereas the classical fast Fourier transform on the same 2-to-the-n amplitudes would take on the order of n times 2-to-the-n operations. The exponential gap is not because the quantum computer 'tries all inputs'; it is because the transform acts on amplitudes in place, and only the final measurement collapses the superposition.

Period-finding: the quantum subroutine, stage by stage

The order-finding subroutine uses two registers. The first holds an exponent x in superposition over a range Q chosen to be a power of two larger than N squared; the second will hold the value of a raised to the power x modulo N. The procedure has four stages. First, prepare the first register in a uniform superposition over all exponents by applying a Hadamard gate to each of its qubits. Second, compute a raised to the power x modulo N into the second register by reversible modular exponentiation — this is the only expensive arithmetic, and it is repeated squaring, entirely standard. Third, apply the Q F T to the first register. Fourth, measure the first register.

The entanglement created in stage two is what makes the trick work. After modular exponentiation, the first register's amplitude is spread over exactly those exponents that produce the same second-register value, and those exponents form an arithmetic progression with common difference r — the period. The Q F T in stage three converts that progression into sharp peaks at multiples of Q over r, and the measurement in stage four samples one such peak.

Nothing in this loop is heuristic. The modular exponentiation dominates the cost, and it is the same modular arithmetic a classical implementation would use, made reversible so it can run on qubits. The Q F T is cheap by comparison. A single run yields one measurement outcome close to a random multiple of Q over r; the next section turns that one number into r itself.

def order_find(a, N):
    Q = smallest_power_of_two_above(N*N)
    reg1 = uniform_superposition(range(Q))     # Hadamards
    reg2 = modexp(a, reg1, N)                   # reversible: |x>|a^x mod N>
    reg1 = QFT(reg1)                            # concentrates amplitude at kQ/r
    y    = measure(reg1)                        # y is near k*Q/r for random k
    return recover_period(y, Q, N)              # continued fractions

From one measurement to the period: continued fractions

The measurement returns an integer y such that the ratio y over Q is close to k over r for some unknown integer k, with an error smaller than one over twice Q. The task is to recover the fraction k over r in lowest terms from a good rational approximation of it. This is a classical, exact procedure: the continued-fraction expansion of y over Q produces a sequence of convergents, and a theorem of Diophantine approximation guarantees that when Q exceeds N squared, the fraction k over r appears among those convergents. The denominator of that convergent is a candidate for r.

Because k might share a factor with r, one run can return a proper divisor of the period rather than the period itself. The remedy is cheap: run the subroutine a small constant number of times and take the least common multiple of the recovered denominators, which equals r with high probability after only a few repetitions. This repetition is why Shor's algorithm is a bounded-error quantum polynomial-time procedure rather than a deterministic one — correctness is a probability driven above any desired threshold by a handful of independent runs.

The continued-fraction step is worth emphasizing because it locates the algorithm's cleverness precisely. The quantum register does not hand you r; it hands you a random rational near a multiple of one over r, and a two-hundred-year-old piece of number theory finishes the job.

Complexity: where the exponential gap comes from

Let n be the bit-length of N. The dominant cost per run is the reversible modular exponentiation, which with schoolbook arithmetic is on the order of n cubed gate operations, and with fast integer multiplication reduces to roughly n squared times poly-logarithmic factors. The Q F T adds only order n squared gates, and the continued-fraction post-processing is classical and negligible. A constant number of runs suffices, so the whole algorithm is polynomial in n — that is, polynomial in the number of digits of N.

Contrast this with the best known classical factoring algorithm, the general number field sieve, whose running time is sub-exponential: it grows like the exponential of a constant times the cube root of n times the square of the logarithm of n. Sub-exponential is faster than exponential but far slower than polynomial. The practical consequence is the entire cryptographic concern: doubling the key size roughly squares the classical work but only polynomially increases the quantum work. There is no key size at which RSA or finite-field Diffie-Hellman remains safe against a sufficiently large fault-tolerant quantum computer.

The same period-finding machinery solves the discrete logarithm problem — find x given a generator g and the value g raised to the power x in a finite group — by finding the period of a two-variable function. Because elliptic-curve cryptography rests on discrete logarithms, it falls to the same algorithm. The reduction is uniform across the public-key primitives in deployment today.

What the algorithm assumes: exact, error-free qubits

Read literally, the subroutine assumes ideal qubits: superpositions that do not decohere, gates that apply exactly, and a Q F T whose phase rotations are perfect. Physical qubits are none of these. The rotations in the Q F T become vanishingly small for distant qubit pairs and can be truncated, which is tolerable, but the deeper problem is that a computation deep enough to factor a cryptographic modulus involves far more gate operations than any physical qubit survives before an error corrupts it.

This is why the algorithm's difficulty has migrated entirely into fault tolerance. To run Shor's short logical circuit, each logical qubit must be encoded across many physical qubits using a quantum error-correcting code so that errors are detected and corrected faster than they accumulate. The surface code of Fowler and colleagues (2012) is the leading candidate, and the resource study of Gidney and Ekerå (2021) estimates that factoring a 2048-bit RSA modulus would take on the order of twenty million noisy physical qubits running for hours — an engineering target, not a mathematical obstacle.

The distinction matters for anyone reasoning about risk. Shor's algorithm does not get better or worse; it is a fixed, proven reduction. What changes over time is only the size and quality of the hardware. That is precisely the variable Mosca (2018) folds into a migration-timing argument: the threat clock is set by hardware progress against the shelf-life of the data you are protecting, not by any doubt about the algorithm.

What collapses, and what this does not touch

The primitives that fall to a large fault-tolerant quantum computer are exactly those whose security reduces to integer factoring or discrete logarithms: RSA encryption and signatures, finite-field Diffie-Hellman key exchange, the digital signature algorithm, and elliptic-curve variants including elliptic-curve Diffie-Hellman and the elliptic-curve digital signature algorithm. Their security parameter offers no refuge, because the quantum cost grows only polynomially in it.

What Shor's algorithm does not touch is equally important to state precisely, since it bounds the response. Symmetric ciphers and hash functions do not reduce to period-finding; the quantum tool that applies to them is unstructured search, a different algorithm with only a quadratic — not exponential — advantage, which is comfortably countered by moderately larger keys and digests. And the post-quantum public-key schemes now standardized rest on problems (structured lattices, error-correcting codes, hash trees, isogenies) for which no polynomial-time quantum algorithm is known. Shor's reduction is powerful but specific: it dissolves the number-theoretic assumptions, and only those.

The honest summary is a narrow, sharp claim. There exists a known, proven, polynomial-time quantum algorithm that breaks every deployed public-key primitive based on factoring or discrete logs, contingent only on hardware that does not yet exist but faces no known fundamental barrier. That single sentence is the entire basis of the migration to post-quantum cryptography.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

key_exchange:
  require_hybrid: true          # classical + PQC KEM both present
  forbid_sole:                  # fail if any of these is the only KEX
    - rsa_kex
    - ffdhe_only
    - ecdh_only
signatures:
  allow: [ml-dsa, slh-dsa, hybrid-ecdsa-mldsa]
audit:
  data_shelf_life_years: required   # every secret tagged for HNDL ranking

Glossary

Multiplicative order (period) r

The smallest positive exponent r for which a raised to the power r is congruent to 1 modulo N; the period of the modular-exponentiation function.

Quantum Fourier Transform (QFT)

A unitary that maps a basis state x to a uniform superposition of states y with phase proportional to xy/Q, concentrating amplitude on the frequencies of a periodic input.

Order-finding / period-finding

The problem of computing the period r of a periodic function; the quantum subroutine at the heart of Shor's algorithm.

Continued-fraction recovery

A classical procedure that extracts the exact fraction k/r in lowest terms from a sufficiently accurate rational approximation of it.

General number field sieve (GNFS)

The fastest known classical factoring algorithm, with sub-exponential running time in the bit-length of the modulus.

Fault tolerance

Encoding logical qubits across many physical qubits with a quantum error-correcting code so errors are corrected faster than they accumulate.

References

1. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (SIAM J. Comput., 1997)
2. Grover, A Fast Quantum Mechanical Algorithm for Database Search (STOC, 1996)
3. Gidney & Ekerå, How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits (Quantum, 2021; arXiv:1905.09749)
4. Fowler, Mariantoni, Martinis & Cleland, Surface codes: Towards practical large-scale quantum computation (Phys. Rev. A, 2012; arXiv:1208.0928)
5. Mosca, Cybersecurity in an era with quantum computers: will we be ready? (IEEE Security & Privacy, 2018; arXiv:1512.06466)