Shor’s Algorithm Explained: The Quantum Threat Driving Post-Quantum Cryptography

Shor’s algorithm is a quantum algorithm that finds the prime factors of a large number far faster than any known classical method. On a large enough, error-corrected quantum computer it would break RSA encryption. No such computer exists today, and none is close.

It is not the same as Shor’s code, a nine-qubit quantum error-correcting scheme the same researcher published in 1995. The points below are the facts most often misreported about the algorithm; each one is sourced and dated later in this guide.

• What it actually does: it turns factoring into a pattern-finding problem (how often a sequence of remainders repeats) and uses a quantum computer for that one step only.
• What it threatens: public-key schemes built on factoring or discrete logarithms, such as RSA, Diffie–Hellman and elliptic-curve cryptography. AES and SHA-2 are not broken by it.
• What has been demonstrated: only tiny numbers, and several celebrated “records” used circuits built with the answer already known.
• What it would take: published estimates for a 2048-bit RSA key fell from about 20 million noisy qubits (2019) to under one million (2025). Both remain far beyond any machine built so far.
• Why migration started anyway: “harvest now, decrypt later”. Encrypted data recorded today could be read once a capable machine exists.
• The response: NIST published its first three post-quantum standards on 13 August 2024, and India’s Department of Science and Technology set critical-infrastructure migration milestones running to 2029.

In short, Shor’s algorithm proves that one family of cryptography will stop being safe; it is not evidence that it already has. The rest of this guide explains why finding a repeating pattern cracks factoring, how far away a capable machine is, and what is already replacing the vulnerable schemes.

Why Shor’s Algorithm Threatens RSA and Other Public-Key Cryptography 

Most secure connections rely on public-key cryptography, and its most widely deployed forms rest on one assumption: some maths problems are easy to set up but practically impossible to reverse. Shor’s algorithm is a threat because it makes exactly those problems easy.

Multiplying two large primes takes a computer microseconds. Recovering the primes from their product, a semiprime (a number with exactly two prime factors), is as far as anyone knows extraordinarily hard for a classical computer. RSA is built on that one-way asymmetry.

The asymmetry sits under a lot of everyday infrastructure. RSA and the related elliptic-curve schemes protect the key exchange and certificates behind HTTPS, the signatures that prove a software update is genuine, and much of the machinery for storing and checking credentials.

The best known classical attack, the general number field sieve, has a running time that grows sub-exponentially with key length: faster than any polynomial, slower than a pure exponential. In practice that is lopsided. Adding bits costs the legitimate user very little and makes the attacker’s job enormously harder, which is why RSA keys can simply be lengthened as computers improve.

Shor’s algorithm removes that lopsidedness. Its running time grows only polynomially with key length, so a longer key no longer buys meaningful safety against a quantum computer large enough to run it.

The most common misconception is that it breaks “all encryption”. It breaks the public-key family whose security rests on factoring or on a close relative, the discrete logarithm problem. The table shows where each family of cryptography stands.

Cryptography family	Common examples	Effect of a large quantum computer
Factoring-based public key	RSA encryption and signatures	Broken by Shor’s algorithm
Discrete-log public key	Diffie–Hellman, DSA	Broken by Shor’s algorithm
Elliptic-curve public key	ECDH, ECDSA	Broken by a variant of Shor’s algorithm
Symmetric ciphers	AES	Not broken; longer keys such as AES-256 keep a wide margin
Hash functions	SHA-2, SHA-3	Not broken; affected far less

The weaker threat to symmetric ciphers comes from a different algorithm. Grover’s algorithm gives a quadratic speedup on unstructured search, not an exponential speedup on one structured problem; roughly, it halves a key’s effective strength, and doubling the key length restores the margin.

That split explains the shape of the response. Post-quantum cryptography replaces the public-key layer; AES and SHA-2 largely stay where they are.

How Shor’s Algorithm Works: From Factoring to Quantum Period Finding 

The algorithm is a chain of four links: factoring becomes a period-finding problem, a quantum computer finds the period quickly, and ordinary arithmetic turns the period into factors. Only one link needs quantum hardware, and understanding the first link is what makes the rest make sense.

How Shor’s Algorithm Turns Factoring Into a Period-Finding Problem 

Pick the number you want to factor and a smaller starting number. Multiply the starting number by itself over and over, keeping only the remainder after dividing by the first number each time. The remainders always fall into a repeating cycle, and the length of that cycle hands you a factor.

Here it is with real numbers. Take 21 (which is 3 × 7) and the starting number 2. Keep multiplying by 2, and whenever the result reaches 21 or more, subtract 21. Every row can be checked on paper.

Step	Calculation	Remainder after dividing by 21
1	2	2
2	2 × 2 = 4	4
3	4 × 2 = 8	8
4	8 × 2 = 16	16
5	16 × 2 = 32, and 32 − 21 = 11	11
6	11 × 2 = 22, and 22 − 21 = 1	1
7	1 × 2 = 2	2 (the cycle restarts)
8	2 × 2 = 4	4

The sequence 2, 4, 8, 16, 11, 1 repeats forever, because once the remainder hits 1, multiplying by 2 takes you straight back to the start. The length of the repeat, 6, is called the period (mathematicians also call it the order).

Turning the period into factors takes four lines of school arithmetic. You halve the period, look up the remainder at that step, and compare its neighbours with 21.

1. Half the period is 3, and the remainder at step 3 is 8.
2. Take one less and one more than 8: that gives 7 and 9.
3. Find the largest number that divides both 7 and 21 (their highest common factor): 7. Do the same for 9 and 21: 3.
4. So 21 = 3 × 7. Factored.

How Shor’s Algorithm Uses Superposition, Interference, and the Quantum Fourier Transform 

The quantum step has two phases. First it builds a single quantum state that contains the whole repeating pattern; then it uses interference so that the one measurement you are allowed to take reveals the period instead of a random value.

In the first phase, the quantum computer evaluates the remainder sequence across a huge range of step numbers in superposition: one quantum state holding all of those inputs at once, each with an amplitude. After this, the repeating pattern is genuinely present in the state.

But a superposition can’t be read out directly. Measuring it returns one random outcome, and a single random remainder tells you nothing about how long the cycle is.

The second phase fixes that with the quantum Fourier transform (QFT). The QFT is a periodicity detector: given a state carrying a hidden repeating pattern, it makes the amplitudes interfere so that outcomes unrelated to the period cancel out and outcomes tied to the period reinforce each other.

This is also why “a quantum computer tries every answer at once” is the wrong picture. Evaluating many inputs in superposition is only the set-up; the speedup comes from interference steering probability onto the few outcomes that encode the period.

Which Parts of Shor’s Algorithm Are Classical and Which Parts Are Quantum? 

Most of Shor’s algorithm runs on an ordinary computer. The quantum machine is called once, as a subroutine, to find the period, and it hands back a single number; the table walks the whole algorithm end to end.

Step	Runs on	What happens
1. Rule out easy cases	Classical	Check the number isn’t even or a power of a single prime
2. Pick a starting number	Classical	Choose one at random; if it already shares a factor with the target, you are done
3. Find the period	Quantum	Compute the remainder sequence in superposition, apply the QFT, measure
4. Read off the period	Classical	Continued fractions convert the measured number into a candidate period
5. Check the period	Classical	It must be even and give a useful result; if not, go back to step 2
6. Compute the factors	Classical	Two highest-common-factor calculations give the two primes

The takeaway most readers have never been told: a quantum computer running Shor’s algorithm does exactly one job, order finding. Everything before and after it is ordinary code, which is why the algorithm is best understood as a classical program with one quantum call inside it.

How Many Qubits Are Needed to Break RSA-2048 With Shor’s Algorithm? 

The honest answer is an estimate, not a fact: researchers publish detailed engineering calculations under stated assumptions, and those numbers have fallen sharply. The best-known figures for breaking a 2048-bit RSA key dropped roughly twentyfold between 2019 and 2025.

These estimates count physical qubits, the actual noisy hardware elements. Most of those qubits are spent on error correction, bundling many physical qubits into each reliable logical qubit using a surface code, a standard grid-based error-correcting layout. The two landmark estimates share the same hardware assumptions, which makes them directly comparable.

Estimate	Qubits and runtime	Assumptions and what changed
Gidney and Ekerå (preprint 2019; Quantum, April 2021)	About 20 million noisy qubits; about 8 hours	Square grid with nearest-neighbour links; 0.1% gate error; 1-microsecond surface-code cycle; 10-microsecond reaction time
Gidney (arXiv, May 2025)	Fewer than 1 million noisy qubits; under a week	Same assumptions; savings from approximate residue arithmetic, yoked surface codes and magic-state cultivation

Read these as a research trajectory, not a countdown. Each figure depends on its assumptions, and a uniform 0.1% error rate across a million-qubit machine is itself far beyond current engineering. Estimates will keep moving, and not only downward: new obstacles can push them back up.

Other hardware approaches have built larger arrays of physical qubits in the lab, but none operate at the scale and error rates these papers assume. The gap is orders of magnitude, not a final push.

Harvest Now, Decrypt Later: Why Organizations Are Migrating to Post-Quantum Cryptography 

If no quantum computer can break RSA today, why is anyone in a hurry? Because encrypted data can be recorded now and stored until the capability exists, so the risk begins when the data is sent, not when the machine is built.

The attack is simple. An adversary captures encrypted traffic, including the key-exchange handshake at the start of each session, and keeps it. If that handshake relied on RSA or elliptic curves, a future machine running Shor’s algorithm could recover the session keys and read everything that followed.

That makes long-lived secrets the ones at risk. Health records, state and diplomatic communications, long-lived intellectual property and biometric data all need to stay confidential for decades, and each is exposed the moment it crosses the wire. India’s February 2026 task force report on quantum-safe migration names this “harvest now, decrypt later” risk as one of its central drivers.

Be precise about what this is. It is a real, widely accepted concern and the main reason serious migration is underway. It is not an evidence that anything has been broken, and it mostly threatens confidentiality: a forged digital signature would need a capable quantum computer at the moment of forging, so signatures are less exposed to harvesting.

The standard way to decide whether you are late comes from Michele Mosca, who set it out in a 2015 paper later published in IEEE Security & Privacy (2018); it is often called Mosca’s inequality. It compares three durations.

1. Shelf life (x): how many years must this data stay secret?
2. Migration time (y): how many years will it take to move your systems to quantum-safe cryptography?
3. Threat timeline (z): how many years until a quantum computer capable of running Shor’s algorithm at scale exists?

If x + y is greater than z, data you send today will still need protecting when it becomes readable, so you are already behind. The uncomfortable part is that z is unknown, and published predictions vary widely; the inequality is useful precisely because it doesn’t require anyone to name a date.

How Post-Quantum Cryptography Protects Against Shor’s Algorithm 

The defence against Shor’s algorithm is not a quantum technology. Post-quantum cryptography (PQC) is new public-key mathematics, designed to resist both classical and quantum attack, that runs on the computers and networks already in use.

NIST Post-Quantum Cryptography Standards: FIPS 203, FIPS 204, and FIPS 205 

On 13 August 2024, NIST released its first three finalised post-quantum standards and told organisations to start using them immediately. Each replaces a job RSA or elliptic curves do today, and each has a new official name alongside the name it had during the competition.

Standard	Algorithm (earlier name)	What it does
FIPS 203	ML-KEM (CRYSTALS-Kyber)	Key encapsulation for agreeing a shared secret key; the primary standard for general encryption
FIPS 204	ML-DSA (CRYSTALS-Dilithium)	Digital signatures; the primary signature standard
FIPS 205	SLH-DSA (SPHINCS+)	Hash-based digital signatures; a backup built on different maths

Source: NIST’s announcement of the first post-quantum standards. A fourth standard, FIPS 206, will specify FN-DSA, derived from FALCON. According to NIST’s post-quantum cryptography project page (last updated August 2026), FALCON and the backup key-encapsulation algorithm HQC, selected in March 2025, are still going through standardisation.

Why should these resist Shor’s algorithm? ML-KEM and ML-DSA rest on problems about lattices, regular grids of points in hundreds of dimensions. In plain terms, you must recover a secret from a set of equations that have been deliberately blurred with small random errors. There is no repeating pattern whose length gives the secret away, so the period-finding trick at the heart of Shor’s algorithm has nothing to grip.

SLH-DSA takes a different route: its security rests on hash functions, which Shor’s algorithm doesn’t touch. For all three standards, quantum resistance is a belief backed by years of public cryptanalysis rather than a mathematical proof, which is why NIST keeps backups in the pipeline.

One boundary worth stating clearly: post-quantum cryptography is new mathematics that runs on ordinary computers and can be deployed as a software update, while quantum key distribution is a hardware-based physics approach to exchanging keys that needs dedicated equipment and solves a narrower problem.

Shor’s algorithm is the clearest example of a quantum computer doing something genuinely different, and the reason a generation of security and systems work is being rethought. If you want that grounding formally, alongside how quantum and AI methods are being applied, look at the Certification in Applied Quantum Computing and AI from IIT Delhi.

Frequently Asked Questions About Shor’s Algorithm