Shor’s Algorithm Explained: Example, RSA and Qubits
Quick answer: Shor’s algorithm, discovered by Peter Shor in 1994, is a quantum algorithm that factors whole numbers in time polynomial in their number of digits, far faster than any known classical method. It turns factoring into finding the period of a^x mod N: a quantum routine finds the period, and ordinary arithmetic (greatest common divisors) recovers the factors. A large error-corrected quantum computer could use it to break RSA. Published qubit estimates describe proposed machines, not demonstrated attacks.
Facts checked November 22, 2026.
In 1994, Peter Shor, then at Bell Labs, showed that a quantum computer could factor huge numbers quickly. Since RSA encryption depends on factoring being hard, his result turned quantum computing from a curiosity into a security issue. The surprising part is that most of Shor’s algorithm is ordinary number theory you can do by hand. Only one step needs a quantum computer.
The Big Idea: Factoring Is Really Period Finding
Pick a number \(a\) and keep multiplying by it, always taking the remainder mod \(N\). The remainders eventually repeat in a cycle. The length of that cycle is the period \(r\): the smallest positive number with \(a^r \equiv 1 \pmod{N}\). Shor’s insight was that if you know the period, you can usually find the factors of \(N\) with simple arithmetic.
Shor’s Algorithm in 5 Steps
- Pick a random \(a\) with \(1 < a < N\).
- Compute \(\gcd(a, N)\). If it is bigger than 1, you have found a factor by luck.
- Quantum step: find the period \(r\) of \(a^x \bmod N\).
- If \(r\) is odd, or \(a^{r/2} \equiv -1 \pmod{N}\), go back to step 1 and try another \(a\).
- Otherwise, \(\gcd(a^{r/2} – 1, N)\) and \(\gcd(a^{r/2} + 1, N)\) are factors of \(N\).
Every step except step 3 runs fast on an ordinary computer, using the Euclidean algorithm for the greatest common divisor (see greatest common factor).
Worked Example: Factoring 15
Let \(N = 15\) and \(a = 7\). Note \(\gcd(7, 15) = 1\), so we continue. Powers of 7 mod 15:
| \(x\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(7^x \bmod 15\) | 7 | 4 | 13 | 1 | 7 |
The cycle 7, 4, 13, 1 repeats, so the period is \(r = 4\), which is even. Then \(a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}\), which is not \(-1 \equiv 14\). Now
\[ \gcd(4 – 1, 15) = \gcd(3, 15) = 3, \qquad \gcd(4 + 1, 15) = \gcd(5, 15) = 5. \]So \(15 = 3 \times 5\). Why does it work? Since \(a^r \equiv 1\), we get \((a^{r/2} – 1)(a^{r/2} + 1) = a^r – 1 \equiv 0 \pmod{N}\). Here \(3 \times 5 = 15\): \(N\) divides the product but neither factor alone, so each shares a piece of \(N\).
When a choice of \(a\) fails: with \(N = 15\) and \(a = 14\), we get \(14^2 = 196 \equiv 1\), so \(r = 2\). But \(14^{1} \equiv -1 \pmod{15}\), and the gcds are \(\gcd(13, 15) = 1\) and \(\gcd(15, 15) = 15\), which are useless. Step 4 catches this, and we simply pick another \(a\). For random choices, most work.
Try one yourself: \(N = 21\), \(a = 2\). The powers mod 21 are 2, 4, 8, 16, 11, 1, so \(r = 6\). Then \(2^3 = 8\), and \(\gcd(7, 21) = 7\) and \(\gcd(9, 21) = 3\). So \(21 = 3 \times 7\).
Where the Quantum Computer Comes In
For a 617-digit \(N\), the period can be astronomically long, so listing powers one by one is hopeless. A quantum computer finds it differently:
- Superposition. Put a register of qubits into an equal combination of many values of \(x\) at once.
- Compute. Calculate \(a^x \bmod N\) into a second register, for all those \(x\) together.
- Inverse quantum Fourier transform. Like finding the beat in a song, it makes amplitudes interfere so that outcomes matching the period’s rhythm become likely and others cancel out.
- Measure and finish classically. Divided by the register size, the measured number lands close to a fraction \(k/r\). Continued fractions turn it into a candidate period, which an ordinary computer checks by testing whether \(a^r \equiv 1 \pmod{N}\); sometimes a few runs are needed.
The quantum computer never “tries all answers and picks the right one.” It uses interference, the same math as waves, to make the period show up. See the math of quantum computing for qubits and amplitudes.
How Much Faster Is It?
The best classical method, the general number field sieve, runs in sub-exponential time: each extra block of digits multiplies the work enormously. Shor’s algorithm needs a number of quantum operations that grows only polynomially with the number of digits, about the cube with standard arithmetic circuits. Real run times also depend on hardware and error correction, but the shape of the growth is what matters: making keys longer slows a quantum attacker modestly and a classical attacker enormously. That is why bigger RSA keys cannot outrun a full-scale quantum computer.
What Has Actually Been Run on Quantum Hardware
| Year | Number factored | Hardware |
|---|---|---|
| 2001 | 15 | IBM team, 7-qubit NMR device (Vandersypen et al., Nature) |
| 2012 | 21 | Photonic experiment using a compiled (simplified) circuit (Martín-López et al., Nature Photonics) |
These are specialized demonstrations: their circuits were simplified using knowledge of the answer, which a real attack could not do. Claims of factoring larger numbers on quantum devices have used similar shortcuts or methods other than Shor’s, so they do not show progress toward breaking RSA. Classical computers, meanwhile, factored the 270-digit RSA-896 in September 2026 (see RSA encryption explained). Running Shor’s algorithm on a 2,048-bit number needs thousands of reliable logical qubits built from many more physical ones.
How Many Qubits Would Break RSA-2048?
First, two terms. A physical qubit is one actual device, such as a superconducting circuit or a trapped atom, and it makes errors. A logical qubit is a reliable qubit built from many physical ones using error correction. Estimates count physical qubits, and each depends on assumed hardware quality.
Selected theoretical estimates, checked November 22, 2026:
| Estimate | Hardware type | Physical qubits | Run time | Key assumptions |
|---|---|---|---|---|
| Gidney and Ekerå, 2019 (published 2021) | Superconducting, surface code | About 20 million | About 8 hours | 0.1% error rate, 1 μs cycles |
| Gidney (Google Quantum AI), May 2025 | Superconducting, surface code | Under 1 million | Under a week | 0.1% error rate, 1 μs cycles, nearest-neighbor wiring |
| Pinnacle architecture (Iceberg Quantum), Feb 2026, revised May 2026 | Quantum LDPC codes | About 94,000 | One month or less | 0.1% error rate, 1 μs cycles, 10 μs reaction time |
| Cain et al., March 2026 | Neutral atoms | As few as 10,000 (more qubits run faster) | Long; for RSA-2048, 10 to 100 times longer than for elliptic curves | Reconfigurable atom arrays, high-rate codes |
| Alice & Bob, Inria and Edinburgh, Oct 2026 (preprint) | Cat qubits | 22,593 (about 45,000 with roughly one bit flip per hour) | 3.14 days or more | Negligible bit flips, 1 μs cycles |
All of these are blueprints, not machines, and the assumptions differ, so the numbers are not directly comparable. The trend is the real news: every year, smarter error-correction codes and circuit tricks cut the requirements, which is why NIST plans to deprecate RSA after 2030 and disallow it after 2035 in favor of post-quantum replacements.
Shor Also Threatens Elliptic-Curve Cryptography
Shor’s method also solves the discrete logarithm problem, the basis of elliptic-curve cryptography (ECC) used for website keys and Bitcoin signatures. Because ECC keys are much shorter than RSA keys, they may fall first: on March 31, 2026, Google Quantum AI estimated that 256-bit elliptic-curve keys could be broken with under 500,000 physical qubits, and Cain and colleagues estimated a few days with 26,000 neutral-atom qubits.
What Shor’s Algorithm Does Not Break
- Symmetric encryption such as AES. Grover’s algorithm gives only a theoretical square-root speedup for key search, with large practical overhead, so AES-256 remains strong.
- Lattice-based cryptography such as NIST’s ML-KEM (FIPS 203) for key exchange and ML-DSA (FIPS 204) for signatures, published August 13, 2024 and designed to resist quantum attacks.
- Hash-based signatures such as SLH-DSA (FIPS 205).
Common Misconceptions
“Quantum computers try every answer at once.” No. Measurement gives one result; interference is what makes the useful result likely.
“RSA is already broken.” No. Quantum hardware has only factored tiny numbers like 15 and 21, with simplified circuits.
“Shor’s algorithm is all quantum.” Only period finding is quantum. The rest is number theory from a high school or first-year course.
Watch: Shor’s Algorithm Explained
If you learn better by watching, these videos are worth your time.
Check Your Understanding
Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.
Answer each question and press Submit to see your result right away.
Frequently Asked Questions
What is Shor’s algorithm in simple terms?
A quantum method for factoring numbers. It turns factoring into finding the repeating cycle (period) of a^x mod N, uses a quantum computer to find that period, and then uses ordinary greatest-common-divisor arithmetic to get the factors.
How does Shor’s algorithm factor 15?
With a = 7, the powers mod 15 are 7, 4, 13, 1, so the period is 4. Then 7^2 mod 15 = 4, and gcd(3, 15) = 3 and gcd(5, 15) = 5, so 15 = 3 × 5.
Who invented Shor’s algorithm?
Peter Shor, a mathematician then at Bell Labs, in 1994. He is now a professor at MIT.
Has Shor’s algorithm broken RSA?
No. Quantum hardware has only factored tiny numbers such as 15 and 21, using simplified circuits. Breaking RSA-2048 needs a large error-corrected quantum computer that does not exist yet.
How many qubits are needed to break RSA-2048?
Estimates keep falling: about 20 million physical qubits in 2019, under 1 million in 2025, and about 94,000 in the 2026 Pinnacle design for a run of a month or less. A March 2026 neutral-atom study says as few as 10,000 atoms, running more slowly, and an October 2026 preprint claims 22,593 cat qubits under optimistic assumptions. All are estimates, not demonstrations.
Why is Shor’s algorithm faster than classical factoring?
Its number of quantum operations grows polynomially with the number’s length, about the cube with standard circuits, while the best known classical method grows sub-exponentially, so the gap becomes enormous for large keys.
Keep Exploring
- RSA Encryption Explained: A Simple Step-by-Step Example
- The Math Behind Quantum Computing: A Beginner’s Guide
- How AI Predicts the Next Word: Probability Explained
Sources and Further Reading
- Shor, Algorithms for quantum computation: discrete logarithms and factoring (FOCS 1994); expanded version arXiv quant-ph/9508027
- Vandersypen et al., Experimental realization of Shor’s quantum factoring algorithm using NMR (Nature, 2001)
- Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (arXiv 2505.15917)
- Webster et al., The Pinnacle Architecture (arXiv 2602.11457)
- Cain et al., Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits (arXiv 2603.28627)
- Scott Aaronson: On reducing the cost of breaking RSA-2048 to 100,000 physical qubits (Feb 2026)
- Quantum Brief: 22,593 qubits and 3.14 days to break RSA-2048 (Oct 30, 2026)
- The Quantum Insider: Three papers in three months rewriting the quantum threat timeline (Mar 31, 2026)
Related to This Article
More math articles
- Delaware DeSSA Grade 8 Math Free Worksheets: Printable Test-Prep Worksheets with Answer Keys
- Printable Calendar
- The Best Grade 3 Math Book for North Dakota Students
- Full-Length 6th Grade MCAS Math Practice Test-Answers and Explanations
- 8th Grade WVGSA Math Worksheets: FREE & Printable
- 8th Grade Wisconsin Forward Math Worksheets: FREE & Printable
- FREE 8th Grade NYSE Math Practice Test
- How to Prepare for the HiSET Math Test?
- Picture Perfect Inequalities: How to Graph Solutions of Two-Step Inequalities
- Probability and Statistics for Beginners: A Friendly Intro


What people say about "Shor’s Algorithm Explained: Example, RSA and Qubits - Effortless Math"?
No one replied yet.