Shor's algorithm
Also known as: Shor algorithm, quantum factoring algorithm, Shor's factoring algorithm
Shor's algorithm is a quantum algorithm that can factor large numbers and solve related problems exponentially faster than any known classical method.
That matters because RSA and elliptic-curve cryptography, which protect much of the internet, rely on those problems being hard. While no quantum computer can run it at a scale that threatens real encryption yet, the risk is serious enough that governments have set deadlines to replace vulnerable cryptography.
Shor's algorithm, explained at three levels
At home
Much of online security relies on a maths puzzle: it's easy to multiply two big prime numbers, but extremely hard to work backward and find them. Shor's algorithm is a quantum recipe that could solve that puzzle quickly, which would break a lot of today's encryption.
At work
Shor's algorithm is why organizations are being told to prepare for 'post-quantum' cryptography. It doesn't threaten encryption today, but large future quantum computers running it could, so migration planning is starting now.
At home
Shor's algorithm turns factoring into finding the repeating pattern, or period, of a mathematical function. Quantum computers are good at finding periods using a step called the quantum Fourier transform. A classical computer then uses that period to find the factors.
At work
Shor's algorithm threatens public-key systems including RSA, Diffie-Hellman, and elliptic-curve cryptography, used for key exchange and digital signatures. Symmetric encryption like AES is much less affected. Migration involves replacing public-key algorithms with standards such as ML-KEM and ML-DSA, starting with systems that protect long-lived data.
At home
The algorithm prepares a superposition of inputs, computes modular exponentiation into a second register, then applies the quantum Fourier transform to reveal the period through interference. In my opinion, it's the most elegant demonstration of why interference, not raw parallelism, drives quantum speed-ups.
At work
Running Shor's algorithm against RSA-2048 requires fault-tolerant quantum computers with many logical qubits and enormous numbers of gates. Estimates keep falling as algorithms and error correction improve, which is why timelines are uncertain. Organizations should inventory where public-key cryptography is used, prioritize long-lived secrets, and build crypto-agility so algorithms can be swapped without redesigning systems.
Real-world examples
At home
Aisha read that quantum computers could one day break the encryption protecting her online banking. She learned that Shor's algorithm was the reason, but also that banks and browsers were already adding post-quantum protections.
At work
Thomas leads security architecture at a Canadian insurer. Because Shor's algorithm threatens RSA and elliptic-curve cryptography, he started an inventory of where they're used, prioritizing systems that store customer data for decades.
How it compares
| feature | Shor's algorithm | Grover's algorithm |
|---|---|---|
| Problem solved | Factoring and discrete logarithms | Unstructured search |
| Speed-up | Exponential (superpolynomial) | Quadratic |
| Threat to cryptography | Breaks RSA and elliptic-curve cryptography | Weakens symmetric keys modestly |
| Defence | Switch to post-quantum algorithms | Use longer keys, such as AES-256 |
| Published | 1994 | 1996 |
Shor's algorithm is the serious cryptographic threat; Grover's is manageable with longer keys.
For analysts
The quantum threat to encryption is a migration project, not a panic. I'd start with an inventory of cryptography in your systems and vendors, because you can't plan a replacement for what you can't find.
History & origin
Mathematician Peter Shor, then at Bell Labs, published his algorithm in 1994, showing that a quantum computer could factor integers and compute discrete logarithms efficiently. It transformed quantum computing from a curiosity into a strategic concern. In 2001, IBM researchers used a seven-qubit nuclear magnetic resonance device to factor 15, a symbolic demonstration. Estimates of the resources needed to break RSA-2048 have fallen over time: a 2019 estimate suggested about 20 million noisy qubits, and a 2025 estimate by Google researcher Craig Gidney lowered that to under a million running for about a week. NIST published its first post-quantum cryptography standards in August 2024. In my view, Shor's algorithm is the single biggest reason governments fund quantum research and migrate their cryptography.