Shor's Algorithm and the Quantum Threat to RSA and ECC

Shor's algorithm is a quantum algorithm that factors large integers and computes discrete logarithms in polynomial time, tasks believed to be intractable for classical computers. Because the security of RSA, Diffie-Hellman, and elliptic-curve cryptography (ECC) rests entirely on the hardness of exactly those problems, a large fault-tolerant quantum computer running Shor's algorithm would break the public-key cryptography that secures the internet. Understanding how it works is essential for anyone planning a defensive migration to post-quantum cryptography.

Why RSA and ECC Are Secure on Classical Computers

RSA encryption uses a public modulus N = p·q, the product of two large secret primes. Recovering p and q from N is the integer factorization problem, for which the best known classical method, the general number field sieve, runs in sub-exponential time. ECC and Diffie-Hellman instead rely on the discrete logarithm problem: given points P and Q = k·P on an elliptic curve, recovering the scalar k takes roughly √n operations classically for a group of size n. Because these costs grow steeply, defenders can stay ahead simply by increasing key sizes, at least against classical adversaries.

The Key Insight: Reducing Factoring to Period-Finding

Shor's breakthrough was to reduce factoring to a period-finding problem that quantum computers solve efficiently. To factor N, pick a random base a coprime to N and consider the function f(x) = aˣ mod N. This function is periodic: there exists an order r such that aʳ ≡ 1 (mod N). Once r is known and is even, and provided a^(r/2) ≢ -1 (mod N), the values gcd(a^(r/2) ± 1, N) reveal nontrivial factors of N.

The classical steps here are easy. The hard part, finding r, is where quantum mechanics provides an exponential speedup.

Inside Shor's Algorithm

The overall procedure interleaves classical and quantum steps:

# Factor N with Shor's algorithm
1. Pick random a in [2, N-1]
2. if gcd(a, N) > 1: return gcd(a, N)        # lucky classical factor
3. Use the quantum subroutine to find r,     # r = order of a mod N,
   the period of f(x) = a^x mod N            # via superposition + inverse QFT
4. if r is odd or a^(r/2) == -1 (mod N): retry from step 1
5. return gcd(a^(r/2) - 1, N), gcd(a^(r/2) + 1, N)

Order Finding

The quantum subroutine prepares a large superposition over input values x, computes aˣ mod N into a second register through reversible modular exponentiation, and thereby entangles inputs with outputs. Measuring the output register collapses the input register to a superposition of exactly those x values that share the same function value, spaced apart by the period r.

The Quantum Fourier Transform

Applying the inverse quantum Fourier transform (QFT) to that periodic superposition concentrates amplitude on multiples of 1/r. Interference makes measurements near integer multiples of 2ⁿ/r overwhelmingly likely. The QFT is what gives Shor's algorithm its power, running in a number of gates polynomial in the number of qubits, whereas any classical Fourier analysis of the function would require exponentially many evaluations.

Classical Post-Processing

A single measurement yields a value close to j·(2ⁿ/r) for some unknown integer j. The continued fractions algorithm efficiently recovers r from this approximation. A few repetitions give the correct order with high probability, after which the factors follow from the greatest-common-divisor computation above.

Breaking Elliptic-Curve Cryptography

A variant of Shor's algorithm solves the discrete logarithm problem directly, so it defeats ECC, finite-field Diffie-Hellman, and DSA as well. Notably, elliptic-curve systems fall with *fewer* logical qubits than RSA at comparable classical security levels, because ECC keys are far smaller. That efficiency, prized in classical settings, becomes a liability against quantum attackers.

How Powerful Must the Quantum Computer Be

Shor's algorithm needs a fault-tolerant machine, not a noisy prototype. Running it against RSA-2048 requires on the order of a few thousand logical qubits and billions of sequential gate operations. Because each logical qubit must be encoded across many physical qubits by quantum error correction, published estimates put the physical requirement in the millions of qubits, well beyond demonstrated hardware. This gap is why the threat is anticipatory rather than immediate, but it is not a reason for complacency.

Defending Against the Quantum Threat

The defensive response is migration to algorithms whose security does not depend on factoring or discrete logs:

1. Adopt NIST-standardized post-quantum cryptography such as ML-KEM for key establishment and ML-DSA for signatures.
2. Deploy hybrid schemes that combine a classical and a post-quantum algorithm so security holds if either survives.
3. Prioritize long-lived secrets, because encrypted data captured in transit can be stored for future decryption, a strategy known as harvest now, decrypt later.

Key Takeaways

• Shor's algorithm factors integers and solves discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and ECC.
• Its core trick reduces factoring to finding the period of aˣ mod N, which the quantum Fourier transform extracts efficiently.
• Elliptic-curve schemes require fewer qubits to break than RSA at equivalent classical strength.
• A cryptographically relevant machine demands fault tolerance and vast numbers of physical qubits, which has not yet been achieved.
• The defensive answer is a planned migration to post-quantum and hybrid cryptography, prioritizing data with long confidentiality lifetimes.