📖 11 min read | 8 Jun 2026 | Written by G Siva Prakash
The algorithm that changed cryptography before a single practical quantum computer existed — and why your bank account could depend on understanding it.
The Security Behind Your Daily Internet Use
Right now, as you read this, millions of people are logging into bank accounts, completing online payments, sending medical records, and storing private conversations. All protected by a single mathematical assumption: that factoring very large numbers is computationally hard. This assumption is the foundation of RSA encryption, which guards much of the internet’s sensitive data.
What Peter Shor proved in 1994, using nothing but mathematics and theoretical quantum mechanics is that this assumption does not hold on a quantum computer. His algorithm, called Shor’s Algorithm, can factor large numbers exponentially faster than any classical factoring algorithm ever designed.
At the time, practical quantum computers did not exist. They barely exist now at the scale needed. But the discovery sent a shockwave through cryptography that is still being felt today, and is actively reshaping how governments, banks, and tech companies think about future digital security.
This guide will walk you through exactly what Shor’s Algorithm is, how it works, what it means for encryption, and why quantum-resistant cryptography is now a global research priority.
// Direct Answer
Shor’s Algorithm is a quantum factoring algorithm developed by mathematician Peter Shor in 1994. It can find the prime factors of a large number exponentially faster than any known classical algorithm. Because RSA encryption relies on the difficulty of factoring large numbers, a sufficiently powerful quantum computer running Shor’s Algorithm could theoretically break RSA encryption.
What Is Shor's Algorithm?
Definition in Simple Terms
Shor’s Algorithm is a quantum algorithm, a set of instructions designed to run on a quantum computer that solves the problem of prime factorisation. Given a large number N, it efficiently finds the two prime numbers that multiply together to make N.
For small numbers, this is easy. For numbers hundreds of digits long(the kind used in real encryption) it becomes practically impossible for classical computers. Shor’s Algorithm changes that equation completely when run on quantum hardware.
Why Was It Revolutionary?
Before Shor’s work, most computer scientists assumed that quantum computers would only offer modest improvements over classical machines for specific tasks. Shor demonstrated a exponential speedup but not just a little faster, but faster in a way that grows dramatically as the numbers get larger.
For a 2,048-bit RSA key (standard today), a classical computer would need longer than the age of the universe to factor it. Shor’s Algorithm, on a sufficiently powerful quantum computer, could theoretically do it in hours. That gap is not an engineering problem, it is a fundamental difference in how quantum and classical machines process information.
Who Is Peter Shor?
Brief Background
Peter Shor is an American mathematician who, at the time of his discovery, was working at Bell Labs, one of history’s most productive research institutions (the transistor and information theory both came out of Bell Labs). He later became a professor at MIT, where he continues to work on quantum information theory.
His 1994 paper, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” introduced the world to both Shor’s factoring algorithm and a related algorithm for discrete logarithms — two of the most important cryptographic problems in existence.
Why His Discovery Matters
Before Shor, quantum computing was largely theoretical with no clear demonstration of practical advantage over classical computing. Shor’s Algorithm was the first concrete proof that quantum computers could solve a real-world, economically important problem exponentially faster than classical machines. It put quantum computing on the map for governments, intelligence agencies, and the broader computer science community in a way that nothing had done before.
Understanding Prime Factorisation Before Learning Shor's Algorithm
What Is Prime Factorisation?
A prime number is one that can only be divided by 1 and itself — like 2, 3, 5, 7, 11, 13. Prime factorisation means breaking any number down into the prime numbers that multiply together to make it.
Why Is Factoring Hard for Large Numbers?
Multiplication goes one way easily. Give a computer the numbers 104,729 and 15,013, and it multiplies them in a fraction of a second. But give it the result — 1,572,237,677 — and ask it to find the two prime factors without being told what they are, and the process reverses into something genuinely difficult.
The best classical factoring algorithms today use methods that grow in complexity roughly as the square root of the number, or worse. For numbers with hundreds of digits — standard in modern encryption — even the world’s fastest supercomputers cannot factor them in any practical timeframe.
Why Large Prime Numbers Matter for Encryption
RSA encryption specifically relies on choosing two large prime numbers, multiplying them together to create the public encryption key, and keeping the original primes secret as the private key. Anyone who can factor the public key recovers the private key — and can decrypt anything encrypted with it. The security of the entire system is borrowed from factoring difficulty.
How Modern Encryption Depends on Factoring
What Is RSA Encryption?
RSA (named after Rivest, Shamir, and Adleman, who created it in 1977) is the most widely used public-key encryption system in the world. It underpins HTTPS, secure email, banking apps, VPNs, and government communications.
Here is how it works at a high level:
Public Key (shared openly)
Generated by multiplying two large prime numbers together. Anyone can use this key to encrypt a message sent to you. It is mathematically safe to share publicly.
Private Key (kept secret)
The original prime numbers used to create the public key. Only the holder of the private key can decrypt messages. The security of the entire system depends on keeping these primes hidden.
Why Factoring Protects Data
Real-world examples where RSA encryption is active right now:
- Your bank’s website (the padlock icon in your browser) uses RSA to secure your login and transaction data.
- Online shopping platforms encrypt payment card details during checkout with RSA-derived keys.
- Government and military communications use RSA-based systems for classified data.
- Email services use RSA in combination with other protocols to ensure only the intended recipient can read messages.
How Does Shor's Algorithm Work? (Step-by-Step)
Shor’s Algorithm uses a clever mix of classical mathematics and quantum computing. The quantum part does not do everything — it handles the one step that is impossible for classical computers. Here is the full process, using the simple example of factoring 15.
Choose the Number to Factor
We want to factor N = 15. In practice, N would be a 2,048-digit RSA key, but 15 works perfectly for illustration.
Pick a Random Guess Number
Choose a random number a that is smaller than N and shares no common factors with N. For N = 15, let us pick a = 7. This is done classically.
Build a Repeating Mathematical Function
Calculate the sequence: 7¹ mod 15, 7² mod 15, 7³ mod 15 ... ("mod" means the remainder after division.) The results are: 7, 4, 13, 1, 7, 4, 13, 1 ... This sequence repeats. That repetition is the key to everything.
Find the Repeating Period — The Quantum Step
The length of the repeating cycle is called the period. In our example, the period is r = 4 (the pattern repeats every 4 steps). Finding this period in a sequence with a small number is easy. For sequences based on 2,048-digit numbers, finding the period classically is computationally impossible. This is exactly where quantum computing comes in.
Quantum Period Finding via Superposition + Interference
The quantum computer evaluates all possible values of the sequence simultaneously using superposition. Then the Quantum Fourier Transform (explained below) uses quantum interference to make the period r emerge as the dominant result when measured. Incorrect values cancel out; the correct period is amplified.
Apply the Quantum Fourier Transform
The Quantum Fourier Transform (QFT) is a quantum operation that detects hidden periodic patterns in data — the same way a musical tuner detects the frequency (pitch) hidden inside a complex sound. Applied to the superposed quantum states, it makes the period r the answer most likely to emerge from measurement.
Recover the Prime Factors Classically
With r = 4 in hand, classical mathematics takes over. Compute GCD(a^(r/2) − 1, N) and GCD(a^(r/2) + 1, N). With a = 7, r = 4, N = 15: GCD(7² − 1, 15) = GCD(48, 15) = 3 and GCD(7² + 1, 15) = GCD(50, 15) = 5. We recover 3 and 5 — the prime factors of 15. ✓
// The Core Insight
Shor’s Algorithm is mostly classical mathematics, with one quantum step in the middle. The quantum step — period finding via the Quantum Fourier Transform — is the part that is exponentially hard for classical computers. The quantum computer solves it in polynomial time. Everything else is standard number theory.
Why Quantum Computers Are Better at Factoring
Classical Approach: Educated Trial and Error
Classical factoring algorithms try to find the period of a function by computing values one at a time and looking for repetition. For small numbers this works fine. For 2,048-bit numbers, the period can be astronomically large — and finding it by sequential search would take more computational steps than there are atoms in the observable universe.
Quantum Approach: All at Once
A quantum computer places all inputs into superposition simultaneously — evaluating the entire sequence of function values at the same time in a single operation. The Quantum Fourier Transform then uses quantum interference to make the period r emerge as the most probable measurement outcome. Wrong answers cancel out; the right answer is amplified.
| Task | Classical Computer | Quantum Computer (Shor's) |
|---|---|---|
| Factor small numbers (15, 21, 35) | Fast ✓ | Fast ✓ |
| Factor medium numbers (thousands of digits) | Minutes to hours | Seconds ✓ |
| Factor RSA-2048 key (617 decimal digits) | Billions of years ✗ | Hours (on future hardware) |
| Hardware required | Ordinary CPU ✓ | Millions of stable qubits (not yet available) |
Real-World Applications of Shor's Algorithm
Shor’s Algorithm is not just a theoretical curiosity. It has driven concrete real-world research and policy decisions across multiple fields.
Cybersecurity Research
Security teams worldwide use Shor's theoretical capabilities as a benchmark for threat modelling — designing defences for a post-quantum world.
Government Policy
The US National Institute of Standards and Technology (NIST) launched a post-quantum cryptography standardization effort directly in response to Shor's Algorithm.
Academic Research
Shor's Algorithm drives research into quantum error correction, qubit stability, and fault-tolerant quantum computing — all required before it can run at scale.
Quantum Hardware Development
Running Shor's at scale requires millions of stable, error-corrected qubits. This motivates every major quantum hardware programme at IBM, Google, and Microsoft.
Cryptography Analysis
Cryptographers use the algorithmic complexity of Shor's as a yardstick — designing new cryptographic systems that remain hard even for quantum computers.
Financial Security Planning
Major banks and financial institutions are running post-quantum transition programmes now, knowing their encryption infrastructure must be upgraded before practical quantum computers arrive.
Can Shor's Algorithm Break RSA Encryption?
The Short Answer
// Direct Answer
Yes, in theory. Shor’s Algorithm can factor the large numbers that RSA encryption is built on, which would allow an attacker to recover the private key from the public key. In practice, no quantum computer today has enough stable, error-corrected qubits to run Shor’s Algorithm against real RSA key sizes. But the mathematical threat is real, well-understood, and being actively prepared for.
Current Limitations
Running Shor’s Algorithm against a real 2,048-bit RSA key would require an estimated 4,000 to 20 million error-corrected logical qubits, depending on the implementation. The best quantum computers today have hundreds to a few thousand physical qubits — and most of those are noisy and error-prone rather than fault-tolerant.
// Important Distinction
Physical qubits and logical qubits are not the same. A single fault-tolerant logical qubit may require hundreds or thousands of physical qubits to build using current error correction methods. The gap between where quantum hardware is today and where it needs to be for Shor’s Algorithm on RSA-2048 is very large — but not infinite, and the timeline is genuinely uncertain.
Why It Still Matters Now
Even if practical quantum computers capable of running Shor’s at scale are 10–20 years away, the threat has to be addressed now. Here is why: an attacker can record encrypted internet traffic today and decrypt it later once a powerful quantum computer exists. Data that must remain secret for decades — medical records, government intelligence, long-term financial records — is already potentially at risk from “harvest now, decrypt later” strategies.
What Is Quantum-Resistant Cryptography?
Why New Encryption Methods Are Needed
RSA and most current public-key encryption systems are vulnerable to Shor’s Algorithm at scale. That means the global internet infrastructure — trillions of dollars of commerce, healthcare, government communications — needs to upgrade its cryptographic foundations.
What Is Quantum-Resistant Encryption?
Quantum-resistant cryptography (also called post-quantum cryptography) refers to cryptographic algorithms designed to be secure against both classical and quantum computers. These algorithms rely on mathematical problems that Shor’s Algorithm does not solve — problems like finding short vectors in high-dimensional lattices, solving certain coding theory problems, or breaking specific hash functions.
What Is Quantum-Proof Encryption?
“Quantum-proof” is sometimes used interchangeably with quantum-resistant, though technically no algorithm can be proven completely future-proof. The more accurate term is quantum-resistant — meaning no known quantum algorithm, including Shor’s, can efficiently break it. Whether future quantum algorithms might solve these problems differently is an open research question.
How Organizations Are Preparing
In 2022, NIST announced its first set of post-quantum cryptography standards. The selected algorithms — including CRYSTALS-Kyber for key exchange and CRYSTALS-Dilithium for digital signatures — are based on lattice mathematics that Shor’s Algorithm cannot crack. Governments, banks, and tech companies worldwide are now planning migration timelines to replace RSA-based systems with these new standards.
Classical computers: ✓ Secure
Quantum computers: ✗ Vulnerable
Threat: Shor's Algorithm
(at sufficient qubit scale)
Classical computers: ✓ Secure
Quantum computers: ✓ Resistant
NIST-standardised 2022
Migration underway globally
Advantages and Limitations of Shor's Algorithm
| Advantages | Limitations |
|---|---|
| ✓ Exponentially faster factorization than any classical algorithm | ✗ Requires millions of fault-tolerant logical qubits — far beyond current hardware |
| ✓ First algorithm to demonstrate a clear, practical quantum advantage over classical computing | ✗ Extremely sensitive to quantum noise and decoherence — errors corrupt results |
| ✓ Directly influenced global cybersecurity policy and post-quantum standards | ✗ Only useful for factoring-based encryption — does not break all cryptographic systems |
| ✓ Drives innovation in quantum error correction and qubit design | ✗ Probabilistic — may need to be run multiple times to confirm the result |
Shor's Algorithm vs Classical Factoring Algorithms
| Feature | Classical Factoring Algorithm | Shor's Algorithm |
|---|---|---|
| Platform | Classical computer (CPU) | Quantum computer |
| Complexity (large N) | Sub-exponential to exponential | Polynomial ✓ |
| RSA-2048 factoring | Billions of years ✗ | Hours (future hardware) |
| Current practicality | Fully practical today ✓ | Not practical at RSA scale ✗ |
| Encryption impact | Limited — RSA remains secure | Would break RSA encryption ✗ |
| Core technique | Sieve methods, trial division | Period finding + Quantum Fourier Transform |
| Scalability with N | Gets dramatically worse | Scales efficiently ✓ |
The Future of Quantum Factoring and Encryption
The race between quantum hardware and post-quantum cryptography is the defining security challenge of the next decade. Here is where things stand and where they are heading.
- Hardware progress is real but slower than headlines suggest. IBM, Google, and others have crossed 1,000-qubit milestones, but physical qubit count is not the same as fault-tolerant logical qubit count. Meaningful Shor’s at scale requires millions of error-corrected qubits — still years away by most expert estimates.
- Post-quantum standards are now finalized. NIST’s 2022 and 2024 post-quantum standards give organizations concrete algorithms to adopt. Migration is underway in governments, defence agencies, and financial institutions.
- “Harvest now, decrypt later” is an active threat. Adversaries may already be storing encrypted data today, waiting for quantum hardware to mature. Long-lived sensitive data needs post-quantum protection now, not later.
- Quantum-resistant encryption is not optional — it is a timeline question. The prudent assumption for critical infrastructure is that RSA will eventually be crackable. Planning for that transition cannot wait until the hardware arrives.
published
process launched
finalized
quantum at scale
(uncertain)
Key Takeaways
- Shor’s Algorithm is a quantum factoring algorithm published by Peter Shor in 1994 that can factor large numbers exponentially faster than any classical approach.
- RSA encryption’s security depends entirely on the difficulty of factoring large numbers — making it theoretically vulnerable to Shor’s Algorithm at scale.
- The core quantum step is period finding via the Quantum Fourier Transform — this is where the exponential advantage over classical computers comes from.
- No quantum computer today can run Shor’s Algorithm against real RSA key sizes. Millions of fault-tolerant logical qubits are required — far beyond current hardware.
- The “harvest now, decrypt later” threat means sensitive long-lived data is already potentially at risk, making post-quantum migration urgent.
- Quantum-resistant cryptography (post-quantum cryptography) has been standardized by NIST and migration is actively underway across governments and major industries.
- Shor’s Algorithm does not threaten all encryption — only systems based on factoring and discrete logarithms. Lattice-based post-quantum systems are designed to resist it.
