Shor's algorithm and why your bank is nervous

A couple of weeks ago I wrote about Grover’s algorithm, the quantum search trick that gives you a square root speedup and not much more. Near the end of that post I said the real threat to cryptography is Shor’s algorithm. This is the post about why.

Short version: almost every secure connection you make today, to your bank, to your email, to this website, starts with a bit of public-key math. That math is safe because certain problems are believed to be hard for normal computers. Shor’s algorithm makes those problems easy for a big enough quantum computer. Nobody has that computer yet. But the people who protect banks and governments are already acting like someone will, and I think the reasons are worth understanding.

The lock everyone uses

RSA is the classic example. You pick two large primes p and q, multiply them to get N = p * q, and publish N. Anyone can use N to encrypt a message to you or check your signature. Knowing the factorization lets you derive the private key. Factoring is a sufficient way to break RSA, though RSA security is not proved equivalent to factoring.

The whole thing rests on one assumption: given N, finding p and q is impractically slow. Multiplying is easy. Un-multiplying is hard.

How hard? The best public classical result I know of is RSA-250, an 829-bit number, factored in February 2020 by a team using the open-source CADO-NFS software. It took roughly 2,700 core-years of computing.¹ Modern guidance generally calls for RSA moduli of at least 2048 bits. The best classical algorithm, the number field sieve, gets slower fast as the number grows, so 2048 bits is far out of reach.

Elliptic curve cryptography (ECC), which most modern TLS connections and phone apps use for key exchange and signatures, rests on a different problem called the discrete logarithm on an elliptic curve. Different math, same idea: easy one way, hard the other way.

In 1994, Peter Shor showed that a quantum computer could solve both factoring and discrete logarithms in polynomial time.² That result is a major reason quantum computing matters to cryptography.

The trick: factoring is secretly about rhythm

Here is the part that surprised me most. Shor’s algorithm doesn’t attack factoring directly. It uses some old number theory to turn factoring into a different question, and only that different question gets handed to the quantum computer.

The different question is period finding.

Pick any number a smaller than N that shares no factor with N. Now look at the powers of a, but only keep the remainder after dividing by N:

f(x) = a^x mod N

This sequence always repeats eventually. The length of one repeat is called the period, usually written r. So a^r mod N = 1, and then the pattern starts over.

Why would the period help you factor? If a^r mod N = 1, then N divides a^r - 1. If r is even, you can split that:

a^r - 1 = (a^(r/2) - 1) * (a^(r/2) + 1)

N divides the product. As long as N doesn’t fully divide either piece on its own, each piece has to share a factor with N. And finding a shared factor is easy. Euclid’s algorithm computes the greatest common divisor (gcd) of two numbers in a handful of steps, even for huge numbers.

So the recipe is:

1. Pick a random a.
2. Find the period r of a^x mod N. (This is the hard part.)
3. If r is even and a^(r/2) isn’t -1 mod N, compute gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N). Those are factors.
4. If it fails, pick a different a and try again.

Shor showed that for an N like an RSA modulus, a random a works at least half the time, so you usually need only a couple of tries.² Everything except step 2 runs on a regular computer.

Worked example: factoring 15

Fifteen is the “hello world” of Shor’s algorithm. It’s small enough to do by hand, and it’s the number that was famously factored on an actual quantum device in 2001, a 7-qubit NMR experiment at IBM.³

Pick a = 7. Compute the powers mod 15:

x:          0   1   2   3   4   5   6   7   8
7^x mod 15: 1   7   4  13   1   7   4  13   1

7^2 = 49, and 49 mod 15 = 4. 7^3 = 343, and 343 mod 15 = 13. 7^4 = 2401, and 2401 mod 15 = 1. Then it repeats. The period is r = 4.

r = 4 is even, so take a^(r/2) = 7^2 = 49, which is 4 mod 15. Now:

gcd(4 - 1, 15) = gcd(3, 15) = 3
gcd(4 + 1, 15) = gcd(5, 15) = 5

15 = 3 * 5. Done.

Here is a failure too. Try a = 14. The sequence goes 1, 14, 1, 14, ..., so r = 2, and a^(r/2) = 14, which is -1 mod 15. Then gcd(13, 15) = 1 and gcd(15, 15) = 15, both useless. That’s the “pick a different a” case from step 4.

Here is the whole classical wrapper in Python. The only thing it cheats on is find_period, which brute-forces the period. For 15 that’s instant. For a 2048-bit number, that loop would run longer than the universe has existed, and that loop is the exact piece a quantum computer replaces.

from math import gcd
import random

def find_period(a, N):
    # The slow part. Shor's algorithm replaces exactly this function.
    x, value = 1, a % N
    while value != 1:
        value = (value * a) % N
        x += 1
    return x

def shor_classical(N):
    while True:
        a = random.randrange(2, N)
        if gcd(a, N) > 1:
            return gcd(a, N)          # lucky guess, already a factor
        r = find_period(a, N)
        if r % 2 == 1:
            continue
        half = pow(a, r // 2, N)
        if half == N - 1:
            continue                  # a^(r/2) = -1 mod N, try again
        return gcd(half - 1, N)

print(shor_classical(15))   # 3 or 5

How a quantum computer finds the period

This is where I’ll stay at the level of intuition, because the full derivation needs more linear algebra than fits in a blog post. Nielsen and Chuang’s textbook has the complete version if you want it.⁴

The circuit has two groups of qubits. The top group, the counting register, holds the input x. The bottom group holds the output a^x mod N.

Here’s what happens, step by step.

1. Superposition. Hadamard gates put the counting register into an even superposition of every x from 0 to 2^n - 1. With 8 counting qubits, that’s all 256 values at once.

2. Compute the function. The controlled multiplication gates compute a^x mod N into the bottom register for every x in the superposition. Each gate handles one bit of x: the gate on qubit k multiplies by a^(2^k). That’s why the boxes in the diagram say 7^1, 7^2, 7^4, and so on. It’s the same repeated-squaring trick that makes pow(a, x, N) fast in Python.

3. The function’s rhythm gets baked into the state. This is the subtle part. After step 2, each x is tied up with its output. If you imagine measuring the bottom register and getting, say, 4, the top register collapses to only the x values that give 4: 2, 6, 10, 14, .... An evenly spaced comb with spacing r. You don’t know where the comb starts, but you know it’s evenly spaced, and the spacing is the period. (You don’t actually have to measure the bottom register. The math works out the same either way. It just makes the picture easier.)

4. The Fourier transform reads the spacing. If you measured the top register now, you’d get one random tooth of the comb, which tells you nothing. So instead you apply the quantum Fourier transform (QFT). A Fourier transform is the classic tool for finding frequencies in a signal. Feed it a comb with spacing r and it produces a different comb, with sharp peaks at multiples of 2^n / r. The starting offset that you didn’t know disappears into a phase that doesn’t affect the measurement.

5. Measure and do some classical cleanup. You measure the counting register and get a number y close to s * 2^n / r for some random integer s. Divide by 2^n and you get something close to s / r. A classical method called continued fractions turns that decimal back into a fraction and gives you r, or a factor of it.

For 15 and a = 7, with 8 counting qubits, the peaks land exactly on 0, 64, 128, and 192. Divide by 256 and you get 0, 1/4, 1/2, 3/4. Getting 64 or 192 hands you r = 4 directly. Getting 128 gives 1/2, which only tells you r is a multiple of 2, so you check, see that 7^2 mod 15 isn’t 1, and run again. Getting 0 tells you nothing and you run again. A couple of runs is plenty.

The interesting thing, for me, is where the speedup comes from. The QFT itself is cheap. On n qubits it uses about n^2 gates, using the same structure as the classical fast Fourier transform but with Hadamards and controlled phase rotations.⁴ The expensive part of Shor’s algorithm is actually step 2, all that modular multiplication, which with ordinary arithmetic costs roughly n^3 gates for an n-bit number.² Polynomial. Compare that to the number field sieve, which grows faster than any polynomial.

Same as with Grover, the computer is not “trying every factor at once.” Every x gets computed in superposition, sure, but you can only read out one number at the end. The trick is that interference makes the one number you read out carry information about a global property of the function, its period. That only works because factoring has this hidden periodic structure. Unstructured search doesn’t, which is exactly why Grover is stuck at a square root and Shor isn’t.

What breaks, and what mostly doesn’t

Breaks: RSA, Diffie-Hellman, and elliptic curves

Shor’s paper covers discrete logarithms too, using the same period-finding core.² That takes out finite-field Diffie-Hellman and, with more work, elliptic curve cryptography. Roetteler, Naehrig, Svore and Lauter worked out the circuit for 256-bit elliptic curves (the kind behind most TLS key exchanges and many signatures) and got an upper bound of about 2,330 logical qubits, fewer than attacking comparably secure RSA would need.⁵ So the “modern” crypto is, if anything, a slightly easier target than the old stuff.

That covers: the key exchange that starts your HTTPS connection, the certificates that prove a website is who it says it is, SSH keys, code signing, and the signatures on most cryptocurrency transactions. Pretty much all public-key cryptography in wide use.

Mostly fine: AES and hash functions

Symmetric ciphers like AES and hash functions like SHA-256 don’t have that periodic structure. The best known quantum attack on them is Grover’s search, which I went through in the last post. That gives a square root speedup at best, and only if billions of steps run in sequence. NIST’s own FAQ says it expects Grover to give little or no advantage against AES, and that AES-128 should stay secure for decades.⁶ If you want extra margin, AES-256 is the conservative choice. Either way, nobody is rewriting AES.

So the asymmetry is pretty stark. Shor breaks the public-key half of cryptography completely. Grover dents the symmetric half a little.

How big a quantum computer would it take?

This is the question that actually matters for whether your bank should be nervous, and the estimates have been moving.

The qubits in today’s hardware are noisy. To run something as long as Shor’s algorithm, you need error correction, where many physical qubits work together to act as one reliable logical qubit. That overhead is where most of the cost comes from.

In 2019, Craig Gidney and Martin Ekerå estimated that factoring a 2048-bit RSA number would take about 20 million noisy physical qubits running for about 8 hours.⁷ Their assumptions were fairly realistic for superconducting hardware: a physical error rate of 0.1%, a surface code cycle time of 1 microsecond, and qubits connected only to their neighbors on a flat grid.

In May 2025, Gidney published an update: fewer than a million noisy qubits, running for less than a week, using the same hardware assumptions.⁸ The qubit count dropped by about 20x. The savings came from better arithmetic tricks, cheaper ways of storing idle qubits, and a more efficient way to prepare the special “magic states” the circuit needs. The tradeoff is that it runs longer.

To put that in perspective, nobody has publicly shown a machine that can run deep error-corrected circuits for days, let alone with a million qubits. That is still a long way off. The estimated qubit budget fell by about 20x, with a longer runtime. That is an algorithmic tradeoff, not a measure of how many years closer the hardware is. That’s the part I think people should pay attention to.

I also want to be honest about the “Shor has already been run” headlines. The 2001 experiment factored 15 with a circuit simplified for that specific number.³ Smolin, Smith and Vargo later pointed out that if you are allowed to simplify the circuit using knowledge of the answer, you can “factor” huge numbers with almost no qubits, and the real measure of difficulty is the length of the period, not the size of the number.⁹ Small demonstrations are good physics. They aren’t evidence that anyone is close to breaking real keys.

Harvest now, decrypt later

So if the machine might be a decade or more away, why is anyone nervous today?

Because of a threat with a very literal name: harvest now, decrypt later. An adversary records encrypted traffic today, stores it, and waits. When a large enough quantum computer exists, they run Shor on the key exchange and read everything. NIST’s transition document calls this one of the main reasons the move to post-quantum cryptography is urgent, especially for data that has to stay secret for years, like government secrets or medical records.¹⁰

The same document describes a simple way to think about the timing, often called Mosca’s theorem. Let X be how many years your data needs to stay secret, Y how many years it takes you to migrate, and Z how many years until a cryptographically relevant quantum computer exists. If X + Y is bigger than Z, you’re already late.¹⁰

For a bank, X might be a decade or more for some records. Y, for an organization with decades of legacy systems, is not short either. That’s the nervousness in the title.

What’s replacing RSA

The good news is that replacements exist and are standardized. In August 2024, NIST published its first three post-quantum standards:¹¹

• FIPS 203, ML-KEM (based on CRYSTALS-Kyber), for establishing a shared secret that a symmetric cipher can then use for encryption.
• FIPS 204, ML-DSA (based on CRYSTALS-Dilithium), for digital signatures.
• FIPS 205, SLH-DSA (based on SPHINCS+), a backup signature scheme built only on hash functions.

ML-KEM and ML-DSA rely on lattice problems, which nobody knows how to attack efficiently with either kind of computer. SLH-DSA uses a completely different idea, so if lattices turn out to have a weakness, there’s still something standing. In March 2025 NIST also picked HQC, a code-based algorithm, as a backup to ML-KEM, again to avoid putting every egg in the lattice basket.¹²

NIST’s draft transition plan, IR 8547, sets the schedule: quantum-vulnerable algorithms like RSA and elliptic curve signatures at the 112-bit security level get deprecated after 2030, and all of them are disallowed after 2035.¹⁰

The migration is also already happening in places you use every day. Chrome moved its TLS key exchange to a hybrid of classical X25519 and ML-KEM in Chrome 131.¹³ “Hybrid” means the connection is safe as long as either one holds, which is a sensible hedge while the new algorithms are still young.

Where I land

What stays with me is the distance between the idea and its consequences. A way of finding periods becomes a way of factoring integers, and that changes the assumptions behind systems people depend on every day. It’s a striking example of an abstract result reaching far beyond the problem it began with.

I don’t know when hardware will be able to run this at the scale that matters for today’s cryptography. The uncertainty makes me more interested in how the transition happens: which systems are easy to replace, which need years, and how people check that the replacements work. The future here involves a lot of careful engineering alongside the quantum computer itself.

Sources