Shor's Algorithm

Shor's algorithm factors large integers in polynomial time — the result that put quantum computing on the map and threatens RSA encryption.

Speedup

exponential over best-known classical

Core

quantum period-finding via QFT

Impact

breaks RSA / ECC at scale

What it does

Factoring reduces to finding the period of the function f(x)=aˣ mod N. Shor prepares a superposition over x, computes aˣ mod N into a register (reversible modular exponentiation built from Toffoli-based arithmetic), then applies the quantum Fourier transform to read off the period. Classical post-processing (continued fractions) turns the period into a factor.

Steps

• Pick random a; classically check gcd(a,N).
• Quantum period-finding: superposition → modular exponentiation → QFT → measure.
• Continued-fraction expansion recovers the period r.
• Factors from gcd(a^{r/2} ± 1, N).

Where it's used

Integer factoring and discrete logarithms — hence its cryptographic significance and the driver behind post-quantum cryptography standards.

In code (Qiskit)

# Shor uses period-finding; conceptually:
# 1) modular exponentiation into a register (Toffoli arithmetic)
# 2) inverse QFT
# 3) measure, continued fractions -> period -> factor