person Tute World Team

Shor's Algorithm Explained

In 1994, mathematician Peter Shor published an algorithm that shocked the cryptography world. Running on a sufficiently powerful quantum computer, it can factor enormous numbers in polynomial time — a task that takes classical computers longer than the age of the universe. It's the algorithm that makes post-quantum cryptography necessary.

What is Shor's Algorithm?

Shor's algorithm is a quantum algorithm for integer factorization — finding the prime factors of a large number. Published by Peter Shor (then at Bell Labs) in 1994, it runs in polynomial time on a quantum computer.

Why that matters: the security of RSA depends on factoring being exponentially hard. Shor's algorithm reduces it to polynomially easy on quantum hardware — completely destroying the mathematical guarantee RSA relies on.

1994 Peter Shor publishes the algorithm (theoretical)
2001 IBM runs Shor's algorithm on a 7-qubit quantum computer, factors 15 = 3 × 5
2012 Factors 21 = 3 × 7 (the current laboratory record for Shor's specifically)
Future Millions of error-corrected qubits needed to break RSA-2048

Classical vs. Quantum Factoring: The Speed Difference

Here's the comparison for factoring an n-bit number:

Best Classical Algorithm

(General Number Field Sieve)

exp( c · n^(1/3) · (log n)^(2/3) )

Sub-exponential. For 2048-bit numbers: effectively impossible in any human timeframe.

Shor's Algorithm

(Quantum)

O( n² log n log log n )

Polynomial — grows gently with key size. For 2048-bit numbers: feasible for a sufficiently large quantum computer.

How Shor's Algorithm Works (Conceptually)

The algorithm has two parts: a classical part and a quantum part. The quantum part is what makes it fast.

Step 1: Reduce factoring to period-finding

Shor's key insight: factoring a number N is mathematically equivalent to finding the period of a specific function. The period is the length r of the cycle in the function f(x) = a^x mod N. Finding this period is something a quantum computer can do very efficiently.

Step 2: Quantum Fourier Transform finds the period

A quantum computer puts many inputs in superposition simultaneously and applies the Quantum Fourier Transform (QFT) — an algorithm that identifies the periodicity of a function exponentially faster than classical Fourier analysis. The QFT is the quantum heart of Shor's algorithm.

Step 3: Classical math derives the factors

Once the period r is found, classical number theory provides a recipe to compute the prime factors of N with high probability. This step runs on a classical computer and is fast.

Plain English: Shor's algorithm uses quantum superposition to simultaneously evaluate a function at many points, then uses quantum interference (via the Quantum Fourier Transform) to extract the pattern. Finding that pattern on a classical computer would require trying exponentially many possibilities. Quantum superposition lets you evaluate all of them at once.

What Exactly Does Shor's Algorithm Break?

Shor's algorithm, and close variants of it, breaks:

  • RSA — by factoring the public modulus to recover the private key
  • Elliptic Curve Cryptography (ECC) — by solving the elliptic curve discrete logarithm problem
  • Classic Diffie-Hellman (DH) — by solving the discrete logarithm problem in finite fields
  • ECDH (Elliptic Curve Diffie-Hellman) — same as ECC
  • DSA and ECDSA signatures — used in TLS certificates, code signing, SSH keys
Everything that protects HTTPS is at risk. The key exchange, the certificate authentication, and the digital signatures in TLS all rely on ECC or RSA. Shor's algorithm breaks all three.

How Far Away Is a Threat?

Breaking RSA-2048 with Shor's algorithm is estimated to require roughly 4,000 logical (error-corrected) qubits running for several hours. To achieve 4,000 logical qubits with today's error rates, you'd need approximately 4 million+ physical qubits.

As of 2025, the largest quantum computers have a few thousand noisy physical qubits. The gap is still enormous. But the trajectory is clear — quantum hardware is improving rapidly.

Why "logical" vs "physical" qubits matters

Physical qubits make errors constantly due to decoherence and imperfect gates. Quantum error correction encodes one reliable "logical qubit" across many physical qubits (typically 1,000–10,000 physical per logical). This overhead is the main barrier to running Shor's at scale. Progress on error correction is accelerating.

Frequently Asked Questions

Could we detect if someone ran Shor's algorithm against our keys?

No. Shor's algorithm is a mathematical computation run offline by the attacker against your public key. It doesn't interact with your systems at all. An attacker computes your private key from the publicly available public key, then uses that private key to decrypt your data. There's no network traffic to detect, no intrusion to spot.

Does Shor's algorithm also break symmetric encryption like AES?

No. Shor's algorithm specifically targets problems related to factoring and discrete logarithms — the mathematical structures in RSA and ECC. AES is based on different mathematics (substitution-permutation networks) and is not vulnerable to Shor's. AES is only weakened by Grover's algorithm, which provides a much more modest speedup.

If Shor's only works on big quantum computers that don't exist yet, why worry now?

Because of the harvest now, decrypt later threat: adversaries with long-term intelligence interests are collecting encrypted data today, storing it, and planning to decrypt it once quantum computers are capable. Data that needs to remain secret for 10–20 years — government secrets, medical records, financial data — is already at risk from today's collection. Migration also takes years, so starting now is essential.

← Why Quantum Breaks Encryption Next: Grover's Algorithm →

Frequently Asked Questions

What will I learn here?

This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.

How should I use this page?

Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.

What should I read next?

Use the navigation below to continue to the next lesson or explore related topics.