Self-Assessment Quiz: Shor's Algorithm

Twenty questions on period finding, the classical reduction, resource requirements, and the cryptographic consequences. Aim for 16+.

Question 1

Shor's algorithm factors an $n$-bit integer in time:

A) $O(2^n)$ B) Polynomial in $n$ C) $O(\sqrt{2^n})$ D) $O(n)$ exactly

Question 2

The best known classical factoring algorithm (GNFS) runs in:

A) Polynomial time B) Sub-exponential time C) Exponential time D) Constant time

Question 3

The quantum part of Shor's algorithm solves:

A) Factoring directly B) Period finding for $f(x) = a^x \bmod N$ C) Discrete logarithm only D) Primality testing

Question 4

The reduction from factoring to period finding is:

A) Quantum B) Classical C) Impossible D) Probabilistic and quantum

Question 5

Given the period $r$ of $a^x \bmod N$ with $r$ even and $a^{r/2}\not\equiv-1$, the factors come from:

A) $\gcd(a^{r/2}\pm1, N)$ B) $r$ itself C) $a \bmod N$ D) $N/r$

Question 6

The probability a random $a$ yields a usable $r$ is:

A) Negligible B) At least 1/2 for typical $N$ C) Exactly 1 D) $1/N$

Question 7

The quantum register in period finding must be large enough that:

A) $2^t > N^2$, so continued fractions resolve $r$ uniquely B) $t = n$ C) $t = \log n$ D) Any size works

Question 8

Post-processing the measured value uses:

A) Continued fractions B) Gaussian elimination C) Newton's method D) Sorting

Question 9

The dominant cost of the quantum circuit is:

A) The QFT B) Modular exponentiation C) The Hadamards D) Measurement

Question 10

Modular exponentiation for an $n$-bit modulus costs roughly:

A) $O(n)$ gates B) $O(n^2)$ C) $O(n^3)$ D) $O(2^n)$

Question 11

Estimated physical qubits to factor RSA-2048 with surface-code error correction:

A) ~2,048 B) ~20,000 C) ~20 million D) ~20 billion

Question 12

Shor's algorithm breaks which of these?

A) AES-256 B) RSA, Diffie–Hellman, and ECC C) SHA-3 D) ML-KEM

Question 13

Elliptic-curve cryptography is:

A) Immune to Shor B) More vulnerable per bit — smaller keys mean fewer qubits needed C) Unaffected D) Only vulnerable classically

Question 14

Doubling RSA key length in response to Shor:

A) Restores security B) Is ineffective — the attack is polynomial, so cost grows only polynomially C) Halves the risk D) Is standard practice

Question 15

The largest number factored by a genuine, non-simplified Shor implementation is on the order of:

A) 15–21 B) 1,000 C) $10^6$ D) RSA-512

Question 16

True or false: Shor's algorithm has been used to break RSA-2048.

Question 17

True or false: The classical part of Shor's algorithm is the hard part.

Question 18

True or false: Shor's speedup is exponential over the best known classical algorithm.

Question 19

Short answer. Explain why "harvest now, decrypt later" makes Shor a present-day concern.

Question 20

Short answer. Some demonstrations "factor" larger numbers using compiled circuits. Why are these results misleading?

Answer Key

Q Ans Note
1 B Roughly $O(n^3)$ with standard arithmetic.
2 B GNFS is sub-exponential, $\exp(O(n^{1/3}\log^{2/3} n))$ — neither polynomial nor fully exponential.
3 B Everything else is classical number theory.
4 B The reduction predates the algorithm and requires no quantum resources.
5 A $a^r \equiv 1$ means $N \mid (a^{r/2}-1)(a^{r/2}+1)$, so the gcds are non-trivial factors under the stated conditions.
6 B At least 1/2 for $N$ with at least two distinct odd prime factors; failures are cheap to detect and retry.
7 A $2^t \ge N^2$ guarantees the continued-fraction expansion resolves $r$ uniquely.
8 A Continued fractions convert the measured $y/2^t$ into a rational with small denominator.
9 B Modular exponentiation dominates; the QFT is comparatively cheap, especially when truncated.
10 C $O(n^3)$ with schoolbook arithmetic; better with advanced multiplication, at the cost of larger constants.
11 C Gidney–Ekerå: ~20 million noisy physical qubits for an 8-hour run.
12 B All the deployed public-key primitives based on factoring or discrete log.
13 B A 256-bit elliptic curve gives 128-bit classical security but needs fewer logical qubits than RSA-2048 — ECC likely falls first.
14 B Polynomial scaling means the attacker's cost grows slowly; the defender's cost grows fast. The trade is hopeless, which is why migration rather than key-lengthening is the answer.
15 A 15 and 21. Larger claims invariably involve simplifications — see Q20.
16 False Not remotely. Existing devices are four to five orders of magnitude short in qubit count.
17 False The classical reduction and continued-fraction post-processing are easy; the quantum modular exponentiation is the hard part.
18 True Polynomial versus sub-exponential is a super-polynomial (commonly called exponential) separation.
19 — Encrypted traffic recorded today can be stored indefinitely and decrypted once a cryptographically relevant machine exists. Any secret whose sensitivity outlives the arrival of that machine is already exposed, so the deadline is set by data lifetime plus migration time, not by the machine's arrival date (Mosca's inequality).
20 — Several demonstrations pre-compute the answer and build a circuit that only works for the known factorization — for instance, choosing a base $a$ whose period is known in advance, then optimizing the circuit using that knowledge. Such a circuit cannot factor an unknown number and does not scale. Genuine implementations must treat $N$ as input and implement general modular exponentiation, which is why the honest record remains at 15 and 21. When you see a large factoring claim, check whether the circuit depends on knowing the answer.