Quantum processor chip held in tweezers under blue light
AI-generated image

Algorithms

What Is Shor's Algorithm, and Why Does It Threaten RSA?

Published · Last updated

Shor's algorithm is the reason quantum computing appears in discussions of Internet security. Introduced by mathematician Peter Shor in 1994, it gives a quantum computer an efficient route to factoring large integers and solving related discrete-logarithm problems. Those are precisely the kinds of problems that underpin widely deployed public-key systems. The important qualification is that the algorithm's mathematical efficiency does not mean today's quantum hardware can routinely break real-world RSA keys.

Why factoring matters

Multiplying two large prime numbers is straightforward for an ordinary computer. Reversing the process (finding the prime factors when only their product is known) becomes difficult for appropriately chosen large inputs. RSA relies on this asymmetry. The public modulus is a product of two secret primes; knowledge of the factors makes it possible to derive information needed to recover the private key from the public parameters.

For a toy example, take 15 = 3 × 5. A human can factor 15 immediately, so there is no security significance in this particular number. The point is to show the structure of the computation. Real cryptographic moduli are vastly larger, and their factors are not obvious. Classical factoring algorithms improve on naive trial division, but no known general-purpose classical polynomial-time factoring algorithm makes appropriately sized RSA moduli easy to break.

NIST explains that Shor's 1994 work transformed quantum computing into a national-security concern because a sufficiently capable machine could factor numbers that conventional cryptographic systems rely on keeping difficult to factor. The concern is specifically about public-key mathematical assumptions, not a claim that all encryption becomes instantly useless.

From factoring to period finding

The key insight is to turn factoring into a problem of finding a period, also called an order. Choose an integer a that is relatively prime to the number N to be factored. Examine the sequence of powers of a modulo N. Because there are only finitely many possible residues, the sequence repeats. Its period r is the smallest positive integer satisfying a^r ≡ 1 (mod N).

Take N = 15 and a = 2. The successive residues are:

PowerResidue modulo 15
2¹2
2²4
2³8
2⁴1

The period is therefore r = 4. Because r is even, compute 2^(r/2) = 4. Then calculate gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. These greatest common divisors reveal the two nontrivial factors of 15.

This example shows why period finding is useful: the period can provide a route to factors through ordinary arithmetic. It also shows why not every choice works. If the selected number shares a factor with N, the greatest-common-divisor step may already expose one; if the period is odd or produces an unhelpful value, the procedure may need another choice. Shor's algorithm is probabilistic rather than a magic single-operation factorizer.

Where the quantum speedup enters

A classical computer can perform the modular arithmetic and greatest-common-divisor calculations. The hard part for large numbers is obtaining the useful period efficiently. Shor's quantum subroutine prepares a superposition, applies modular exponentiation and uses quantum Fourier-transform techniques to extract information about periodicity from measurement outcomes. Classical post-processing then reconstructs a candidate period and tests whether it yields factors.

The quantum Fourier transform is not a device that reads every value of a superposition into a classical list. Measurement yields limited classical information, and the algorithm is designed so interference makes that information useful. Multiple runs and checks can be needed. This distinction matters because popular descriptions sometimes imply that a quantum computer simply tries all candidate factors in parallel and reads the answer. That is not how the algorithm works.

Shor's algorithm is often described as offering an exponential improvement over the best known classical approaches to the relevant mathematical problems. This is a statement about asymptotic computational complexity. It does not remove the substantial costs of reliable quantum gates, error correction, physical qubits, classical control or the implementation of modular arithmetic at cryptographic sizes.

Which cryptography is affected?

RSA is the clearest example because factoring its public modulus undermines its central assumption. Quantum algorithms for discrete logarithms also threaten traditional Diffie–Hellman and elliptic-curve public-key mechanisms. That means the exposure spans both key establishment and digital signatures, though these are different functions and require different replacements.

NIST finalized FIPS 203 (ML-KEM) for post-quantum key encapsulation, FIPS 204 (ML-DSA) for digital signatures and FIPS 205 (SLH-DSA) for stateless hash-based signatures in August 2024. The standards address the need to move away from vulnerable public-key schemes before a future large-scale quantum computer becomes practical. They do not imply that a cryptographically relevant quantum computer already exists.

What Shor's algorithm does not prove

The algorithm does not demonstrate that any announced processor with a particular raw qubit count can factor production RSA keys. Raw physical-qubit counts omit crucial information about error rates, circuit depth, connectivity and the overhead of fault tolerance. A useful security assessment therefore separates three questions: whether the mathematics gives a quantum advantage, whether a hardware platform can execute the required computation reliably, and when a specific cryptographic deployment must migrate.

It also does not establish that every cryptographic primitive is equally vulnerable. Symmetric-key encryption and cryptographic hashes face different quantum attack models from RSA factoring. The practical response is to inventory public-key dependencies, use standardized post-quantum replacements where appropriate and avoid treating speculative hardware dates as security guarantees.

← All news