Shor's Algorithm

What

In 1994, Peter Shor discovered quantum algorithms that can factor large numbers and solve discrete logarithms exponentially faster than classical computers. This was the earthquake that created the quantum threat to cryptography. Shor's algorithm works by finding the period of a mathematical function using quantum Fourier transforms - an operation where quantum superposition gives exponential parallelism. For RSA-2048, a classical computer needs roughly 2^128 operations (billions of years). Shor's algorithm needs only millions of operations on a quantum computer with sufficient qubits and low error rates. Current estimates: breaking RSA-2048 requires about 20 million physical qubits with good error correction, or 4,000 logical qubits. We're not there yet - current systems have hundreds of noisy qubits. But progress is exponential, and most experts estimate 10-15 years. Some conservative estimates say 20-30 years. Some aggressive estimates say 5-10 years. The uncertainty itself demands action.

Why

Shor's algorithm isn't just theoretical - it's been demonstrated on small numbers using small quantum computers, proving the principle works. The only question is scale: when will quantum computers be large and stable enough to run Shor's algorithm on cryptographic key sizes? Intelligence agencies assume adversaries are working on this intensely. The NSA says prepare now because the timeline is uncertain.

Impact

Shor's algorithm is why NSA requires quantum migration by 2035. It's why NIST spent eight years finding post-quantum alternatives. It's why "harvest now, decrypt later" is a real threat. Organizations must assume Shor's algorithm will succeed within their data sensitivity lifetime. If your data needs protection for 10+ years, you need quantum-safe cryptography now - not when quantum computers actually arrive.

Use Cases

Quantum threat assessment and risk modeling, explaining urgency of quantum migration to leadership, justifying quantum security investment, setting migration timelines, understanding cryptographic vulnerabilities, following quantum computing development and threat evolution

Links

https://www.qnulabs.com/blog/ | https://www.youtube.com/c/QNuLabs

Tags

Shor algorithm, Shor's algorithm, quantum factoring, quantum discrete logarithm, RSA threat, ECC threat, quantum cryptanalysis, quantum Fourier transform, quantum period finding, quantum threat to cryptography, cryptographically relevant quantum computer, post-quantum urgency