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

  1. Pick a random \(a\) with \(1 < a < N\).
  2. Compute \(\gcd(a, N)\). If it is bigger than 1, you have found a factor by luck.
  3. Quantum step: find the period \(r\) of \(a^x \bmod N\).
  4. If \(r\) is odd, or \(a^{r/2} \equiv -1 \pmod{N}\), go back to step 1 and try another \(a\).
  5. 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\)12345
\(7^x \bmod 15\)741317

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:

  1. Superposition. Put a register of qubits into an equal combination of many values of \(x\) at once.
  2. Compute. Calculate \(a^x \bmod N\) into a second register, for all those \(x\) together.
  3. 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.
  4. 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

YearNumber factoredHardware
200115IBM team, 7-qubit NMR device (Vandersypen et al., Nature)
201221Photonic 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:

EstimateHardware typePhysical qubitsRun timeKey assumptions
Gidney and Ekerå, 2019 (published 2021)Superconducting, surface codeAbout 20 millionAbout 8 hours0.1% error rate, 1 μs cycles
Gidney (Google Quantum AI), May 2025Superconducting, surface codeUnder 1 millionUnder a week0.1% error rate, 1 μs cycles, nearest-neighbor wiring
Pinnacle architecture (Iceberg Quantum), Feb 2026, revised May 2026Quantum LDPC codesAbout 94,000One month or less0.1% error rate, 1 μs cycles, 10 μs reaction time
Cain et al., March 2026Neutral atomsAs few as 10,000 (more qubits run faster)Long; for RSA-2048, 10 to 100 times longer than for elliptic curvesReconfigurable atom arrays, high-rate codes
Alice & Bob, Inria and Edinburgh, Oct 2026 (preprint)Cat qubits22,593 (about 45,000 with roughly one bit flip per hour)3.14 days or moreNegligible 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.

How Quantum Computers Break Encryption | Shor’s Algorithm Explained (minutephysics). An animated explanation of period finding and the quantum Fourier transform.
How Shor’s Algorithm Factors 314191 (minutephysics). The follow-up, working a full example number by number.
Shor’s Algorithm for Quantum Computing – Computerphile (Computerphile). A computer scientist explains the algorithm on paper.

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.

1. What are the powers of 7 mod 15, starting from 7^1?
Found a bug? Let us know!
2. So what is the period r of 7^x mod 15?
Found a bug? Let us know!
3. With 7^2 = 49, which leaves 4 mod 15, what is gcd(4 − 1, 15)?
Found a bug? Let us know!
4. Which step of Shor’s algorithm needs a quantum computer?
Found a bug? Let us know!
5. With N = 15 and a = 14, the period is 2, but 14 leaves −1 mod 15. What should you do?
Found a bug? Let us know!

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

Sources and Further Reading

Related to This Article

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

No one replied yet.

Leave a Reply