You are reading without signing in. Sign in or continue as guest to take quizzes and keep XP.
Shor's algorithm: the overview
Factoring reduces to period finding; period finding is phase estimation. What is quantum, what is classical, what it costs.
- State the classical reduction from factoring to finding the period of aˣ mod N.
- Identify the quantum step and its cost.
- Explain why no current machine threatens RSA-2048.
- Pick a random a < N. If gcd(a, N) > 1 you are done.
- Find the period r of f(x) = aˣ mod N: the smallest r with aʳ ≡ 1. This is the quantum step.
- If r is even and a^{r/2} ≠ −1 mod N, then gcd(a^{r/2} ± 1, N) are factors. Otherwise try another a (a few tries suffice).
Period finding is phase estimation on the unitary that multiplies by a modulo N: its eigenphases are multiples of 1/r, so the counting register reads k/r and a continued-fraction step recovers r. Everything hard sits in the modular multiplication circuits, which need thousands of logical qubits and millions of gates for a 2048-bit N.
| Step | Classical or quantum | Cost |
|---|---|---|
| Choose a, gcd | classical | trivial |
| Period of aˣ mod N | quantum (QPE) | O((log N)³) gates, 2·log N + extra qubits |
| Continued fractions, factors | classical | trivial |
Record demonstrations factor 15 and 21 with heavily simplified circuits. Breaking RSA-2048 needs roughly 20 million noisy physical qubits running for hours by current estimates, against machines of a few hundred to a thousand qubits today. The threat is real but not imminent, and migration to post-quantum cryptography is already under way.
Which part of Shor's algorithm is quantum?
Sign in to answer and earn XP; you will come back to this lesson.
Why does Shor's algorithm not break symmetric ciphers like AES?
Sign in to answer and earn XP; you will come back to this lesson.
Shor = classical reduction + quantum period finding (phase estimation) + classical post-processing. Exponential speed-up on factoring, far from practical today, already shaping cryptography.
Up next: From an abstract qubit to a device · Hardware and Compilation