sciencebriefs
9:44in productionCh. 1 · A 1994 thought experiment/ 9:44 · ceiling 15 min
Computing & AI · Physics

Shor's algorithm

Shor · 1994

Shor’s algorithm doesn’t break encryption yet—but it proved RSA was never quantum-safe.

Shor’s algorithm is a quantum algorithm for integer factorisation, developed by Peter Shor in 1994. It runs in polynomial time in log N and places factorisation in BQP. It is asymptotically faster than the general number field sieve.

Computing & AIPhysicsAlgorithmsComputingCryptographyAlgorithms across the network →
Chapters & takeaways4
  1. 0:53
    A 1994 thought experiment

    Peter Shor published this in 1994—not as engineering, but as a complexity-theoretic proof.

  2. 2:40
    Two parts: classical + quantum

    It factors integers by finding multiplicative order—a classical reduction plus a quantum subroutine.

  3. 4:32
    Faster in theory, not in reality

    It beats the best classical factoring algorithm asymptotically—not in practice, but in scaling.

  4. 6:06
    Where it reshaped complexity theory

    It places factorisation in BQP, proving quantum computers can solve problems outside P (assuming P ≠ BQP).

Worth your time?

Yes. Study the whole thing.

4.5/ 5
What works
  • Establishes quantum advantage for factorisation in theory
  • Defines the threat model for RSA under quantum attack
  • Separates quantum feasibility from classical hardness
What does not
  • Runs on current hardware
  • Breaks real-world encryption today
  • Proves P ≠ BQP
Study it if
  • Cryptographers
  • Quantum complexity theorists
  • Security engineers planning post-quantum migration
Skip it if
  • Developers building near-term quantum apps
  • Policy makers needing immediate risk assessment
The written brief2 min read

What the work claims

That integer factorisation lies in BQP—the class of problems efficiently solvable by a quantum computer.

Shor proposed several related algorithms, for the factoring problem, the discrete logarithm problem and the period-finding problem. “Shor’s algorithm” usually means the factoring one, and all three are instances of the hidden subgroup problem. For factoring, the quantum gate count is of order (log N)² (log log N)(log log log N) using fast multiplication, and a gate count of this kind shows integer factorisation is in BQP.

How it was done

Shor’s algorithm reduces integer factorisation to order-finding using classical computation, then solves order-finding on a quantum computer via quantum phase estimation and continued fractions.

The classical half is short. Euclid’s algorithm checks whether N is even, and a random integer a is tested with gcd(a, N); a shared factor ends the work. Otherwise a has a multiplicative order r modulo N, and the quantum subroutine exists only to find r. If r is odd, the algorithm restarts with a new a. The quantum circuit uses two registers and phase estimation, and a classical continued-fractions step then recovers the period from the measurements. The runtime bottleneck is quantum modular exponentiation, which is far slower than the quantum Fourier transform and the classical processing.

What holds up

The asymptotic speedup holds: it runs in polynomial time in log N, while the general number field sieve runs in sub-exponential time.

What does not

It does not run on any existing quantum computer. It assumes fault-tolerant, scalable quantum hardware with low error rates—none of which existed in 1994 or exists today.

The demonstrations so far are tiny. In 2001 an IBM group factored 15 into 3 × 5 on a seven-qubit NMR quantum computer. None of these meet the requirements of the algorithm: they compile the circuit using prior knowledge of the answer, and some oversimplify it until it is equivalent to coin flipping. As of 2026, laboratory runs give correct results in only a fraction of attempts, and beating classical computers may need millions of qubits because of the overhead of error correction.

Why it matters beyond the lab

It established a concrete cryptographic vulnerability: widely used public-key encryption (e.g., RSA) would collapse if large-scale quantum computers were built.

RSA is not the only target. Finite-field and elliptic-curve Diffie–Hellman key exchange are schemes the algorithm could also break, assuming a quantum computer with enough qubits that operates without succumbing to noise and decoherence. The result has been called a powerful motivator for building quantum computers, and it has also driven research on post-quantum cryptography: cryptosystems that are secure against quantum computers.

Is it worth your time

Yes—if you need to understand why quantum computing threatens RSA cryptography, or why factoring is not provably hard for quantum machines.

Same field · Computing & AI4 of 46
13:00
Colossus computer1943Tommy Flowers designed Colossus to automate the statistical work of breaking the German Lorenz cipher, betting that a machine built from far more thermionic valves than anyone had tried could run reliably. Ten machines were operating by the end of the war, and the design is now regarded as the first programmable electronic digital computer, though thirty years of official secrecy meant it had little direct influence on the computers that followed.
10:30
Alan Turing1912–1954Turing’s work established formal computability, proved fundamental limits on algorithms, broke wartime ciphers through statistical engineering, and founded mathematical biology with reaction–diffusion theory. It does not claim he built the first computer, solved the Entscheidungsproblem, or proved incompleteness. His definitions and proofs remain operative in computing, cryptography, and theoretical biology.
10:00
George Boole1815–1864Boole gave logic a syntax that could be wired. That syntax works — but nothing he wrote explains why it works in silicon, or how thought maps to switches. His achievement is formal, not physical. His limits are conceptual, not historical.
13:00
P versus NP problemStephen Cook's 1971 theorem proved that one problem, Boolean satisfiability, stands for every problem in NP — a result that didn't resolve P versus NP but explains why cryptography still depends on the question staying open.
Up next in Science

Detection theory

1966 · 13:00

Signal detection theory, formalised in 1954 out of radar research and set out for psychology by Green and Swets in 1966, split a single accuracy score into two things: how well someone can actually tell signal from noise, and how readily they say yes at all.

Play nextBack to Computing & AI
13:00