Shor's Algorithm Explained

Factoring the Unfactorable

Discovered in 1994 by Peter Shor, this quantum computer algorithm mathematically guarantees the rapid factoring of massive integers in polynomial time.

When quantum computers scale to hold enough stable qubits, Shor's Algorithm will systematically dismantle RSA and completely break modern public-key exchanges, requiring a total overhaul of global TLS protocols.

Polynomial Time Cracking

Classical computers factor massive primes via Number Field Sieve methods (sub-exponential time). Shor's algorithm utilizes quantum superposition and Fourier transforms to find the periodicity of a function, successfully reducing prime factoring to polynomial time.

Everyday Example

Imagine a massive ocean full of endless waves. Classical computers try to map the ocean by dipping a bucket in one wave at a time. Shor's Algorithm uses Quantum superposition to exist across all the waves simultaneously. By causing all the wrong waves to mathematically cancel each other out, only the correct wave (the password) is incredibly magnified and seen instantly.

The Deep Mathematics

Shor's leverages the Quantum Fourier Transform (QFT) to compute the period of the modular exponentiation function f(x) = a^x mod N. While the modular exponentiation occurs across an entangled superposition, applying the QFT selectively triggers destructive interference for off-period states, yielding the prime boundaries exponentially faster than classical Number Field Sieve processing.