Home / Quantum from Scratch / Ep 15

Quantum from Scratch · Episode 15 of 19

Shor's algorithm

Shor's Algorithm: Can Quantum Computers Break RSA Encryption?

Watch on YouTubeInstagram

Go deeper

What I say in the video

One algorithm could break the lock on your bank app. Not today.

That lock relies on one fact: multiplying huge primes is easy. Splitting them back is brutally hard.

In 1994, Peter Shor found a quantum shortcut that finds a hidden pattern instead of guessing.

The catch: a 2025 Google estimate says it needs under a million qubits, running under a week.

Today's record array: about six thousand. And the estimates keep falling.

But attackers can copy encrypted data now and unlock it later.

That's why US standards plan to phase RSA out after 2030.

In plain words

Could a quantum computer break the encryption behind your bank app? Here's how Shor's algorithm works, and how far away it really is.

What this Short covers:

  1. RSA encryption relies on one fact: multiplying two large primes is easy, but factoring the product back is extremely hard for classical computers.
  2. In 1994, Peter Shor published a quantum algorithm that factors numbers by finding a hidden repeating pattern (a period) instead of guessing.
  3. A 2025 estimate from Google Quantum AI (Craig Gidney): breaking RSA-2048 would take under 1 million noisy qubits running for under a week.
  4. The largest qubit array reported so far is about 6,100 trapped atoms (Caltech, 2025), and resource estimates keep falling.
  5. "Harvest now, decrypt later": attackers can store encrypted data today and decrypt it once the hardware exists.
  6. NIST's draft transition plan (IR 8547) deprecates RSA and other quantum-vulnerable algorithms after 2030 and disallows them after 2035.
What I simplified

Fine print for the crypto crowd: "the lock on your bank app" = public-key crypto (RSA/ECC) used in key exchange and signatures; Shor breaks both, but not symmetric ciphers like AES. The "hidden pattern" is the period of modular exponentiation, found with the quantum Fourier transform (tomorrow's episode). The 2025 estimate is Craig Gidney (Google Quantum AI): RSA-2048 with fewer than 1 million NOISY physical qubits in under a week (arXiv 2505.15917), and 2026 papers cut it further in simulation. The ~6,100 record is Caltech's trapped-atom array (Nature, Sep 2025): atoms held in superposition, not an error-corrected computer. "Phase out after 2030" = NIST IR 8547 initial public draft: quantum-vulnerable algorithms deprecated after 2030, disallowed after 2035.

Sources (12)
  1. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" (FOCS 1994)dl.acm.org
  2. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits" (2025)arxiv.org
  3. Caltech 6,100-qubit array, Nature (2025)nature.com
  4. NSA/CISA/NIST, Quantum-Readiness factsheet (2023)media.defense.gov
  5. NIST IR 8547 (initial public draft)csrc.nist.gov
  6. nvlpubs.nist.gov
  7. en.wikipedia.org
  8. dblp.org
  9. thequantuminsider.com
  10. caltech.edu
  11. thequantuminsider.com
  12. arxiv.org

One new quantum idea, every week

The next episode in your inbox, with its sources. Free, and one click to unsubscribe.