person Tute World Team

Shor's Factoring Algorithm

In 1994, Peter Shor wrote an algorithm that sent shockwaves through the cryptography world. It can factor large numbers — the basis of RSA encryption — exponentially faster than any known classical method. When large-scale quantum computers arrive, Shor's algorithm could render much of today's internet encryption obsolete.

Why Does Factoring Matter?

RSA encryption — used to secure HTTPS, banking, email, and more — is based on one simple mathematical fact: multiplying two large prime numbers is easy, but factoring their product is practically impossible for classical computers.

Easy (milliseconds)
6,779 × 8,191 = 55,534,589
Hard (years for large numbers)
55,534,589 = ? × ?

RSA uses numbers with thousands of digits. The best classical algorithm (General Number Field Sieve) runs in roughly e^(n^(1/3)) time — super-polynomial, effectively intractable for large n. Shor's algorithm runs in O((log n)³) — polynomial time. That's an exponential speedup.

How Shor's Algorithm Works (Conceptually)

Shor's algorithm reduces factoring to a different problem: finding the period of a modular arithmetic function. Here's the high-level flow:

1
Classical pre-processing: Pick a random number a less than N (the number to factor). Check if gcd(a, N) ≠ 1 — if so, you're done (you found a factor). Otherwise, proceed.
2
Quantum period-finding: Find the period r of the function f(x) = aˣ mod N. This means: what is the smallest r such that aʳ ≡ 1 (mod N)? This is the hard part — done quantumly.
3
Classical post-processing: If r is even and a^(r/2) ≢ −1 (mod N), compute gcd(a^(r/2) ± 1, N). With high probability, these are the prime factors of N.
The quantum magic is in step 2. Finding the period of aˣ mod N classically takes exponential time. The Quantum Fourier Transform (QFT) finds it in polynomial time by expressing the periodic function as a superposition and extracting the period via frequency analysis — exactly what the QFT does.

The Role of the Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the engine of Shor's algorithm. It transforms a superposition of the periodic function f(x) = aˣ mod N into a superposition that has large amplitudes exactly at integer multiples of N/r (where r is the period). Measuring this gives you N/r, and simple arithmetic recovers r.

The classical Fast Fourier Transform (FFT) does the same thing but takes O(n·2ⁿ) operations for n bits. The QFT does it in O(n²) operations — exponentially faster.

We cover the QFT in detail in the next article.

Impact on Cryptography

What Shor's can break

  • RSA — used in HTTPS, TLS, SSH
  • Elliptic Curve Cryptography (ECC) — used in Bitcoin, modern TLS
  • Diffie-Hellman key exchange — used for secure session keys

What Shor's cannot break

  • Symmetric encryption (AES) — Grover's gives √N speedup, but AES-256 remains secure with 128-bit effective security
  • Post-quantum cryptography (PQC) — New algorithms like CRYSTALS-Kyber and CRYSTALS-Dilithium are designed to resist both classical and quantum attacks
  • Hash functions (SHA-3) — Largely unaffected; Grover's only marginally weakens them
The world is already preparing: NIST finalized the first post-quantum cryptography standards in 2024. Major organizations are beginning the "crypto-agility" migration to quantum-safe algorithms — even though large-scale quantum computers capable of running Shor's on real RSA keys don't exist yet. The threat is real enough to act now.

Where Are We Today?

Shor's algorithm requires a fault-tolerant quantum computer with thousands to millions of logical qubits. Today's NISQ-era machines have:

  • 100–1,000 physical qubits (with high error rates)
  • The largest number factored with a quantum computer (using Shor's) so far: 21 = 3 × 7 (2012, IBM)
  • Estimates suggest factoring 2048-bit RSA would need ~4,000 logical qubits with full error correction — likely millions of physical qubits

We're still years or decades from this capability. But the direction is clear, and the cryptography community isn't waiting.

Frequently Asked Questions

Should I be worried about Shor's algorithm right now?

For most people — not immediately. Current quantum computers can't run Shor's on real encryption keys. However, "harvest now, decrypt later" attacks are a real concern: adversaries may be recording encrypted traffic today, planning to decrypt it once quantum computers are powerful enough. Sensitive long-lived data (government, medical) should migrate to post-quantum cryptography soon.

Does Shor's algorithm work on all factoring problems?

Yes — it factors any integer N (that isn't prime or a prime power) in polynomial time. The quantum period-finding subroutine works for any such N. The classical reduction from factoring to period-finding has been known since the 1970s; Shor's insight was the quantum speedup for the period-finding part.

Can quantum computers break Bitcoin?

In principle, Shor's algorithm could attack Bitcoin's elliptic curve cryptography (used to sign transactions). However, this would require quantum computers far beyond current capability. Bitcoin also uses hash functions (SHA-256) that are more resistant. The Bitcoin community could upgrade its cryptography if needed — though coordination would be difficult.

← Grover's Search Next: Quantum Fourier Transform →

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.