Exercises: Chapter 15 — Shor's Algorithm — Factoring Large Numbers in Polynomial Time (and Why It Breaks RSA Encryption)

Exercise 15.1 (Period Finding by Hand). Let $N = 15$ and $a = 2$. Compute the sequence $a^x \bmod 15$ for $x = 0, 1, 2, \ldots$ until you find the period $r$. Verify that $r$ is even and that $\gcd(a^{r/2} \pm 1, 15)$ yields non-trivial factors.

Exercise 15.2 (Modular Exponentiation Circuit Size). For $N = 15$ ($n = 4$ bits), how many qubits does the period-finding circuit require? How many controlled modular multiplications are needed? Estimate the total gate count if each controlled multiplication uses $O(n^2)$ gates.

Exercise 15.3 (Continued Fractions). Suppose a measurement yields $c = 3$ with $2^t = 16$. Compute the continued fraction expansion of $3/16$ and identify which convergent gives the correct period $r = 4$ for $a = 7 \bmod 15$.

Exercise 15.4 (Qiskit Modification). Modify the Qiskit code to factor $N = 21$ using $a = 2$. What is the period? What factors do you obtain? (Hint: you may need to increase the number of qubits and adjust the modular multiplication unitary.)

Exercise 15.5 (RSA Key Breaking). An RSA public key has $N = 33$ and $e = 7$. Use Shor's algorithm (by hand or with Qiskit) to factor $N$, compute $\phi(N)$, find the private key $d$, and decrypt the ciphertext $c = 10$.

Exercise 15.6 (Probability Analysis). Derive the probability that Shor's algorithm succeeds in finding the period $r$ on a single run. Show that the probability is at least $4/\pi^2 \approx 0.405$ when $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$. Hint: use the analysis of QPE success probability from Chapter 16.

Exercise 15.7 (Alternative Bases). For $N = 15$, enumerate all possible choices of $a \in \{2, 4, 7, 8, 11, 13, 14\}$ (the integers coprime to 15). For each $a$, compute the order $r$, check whether $r$ is even and $a^{r/2} \not\equiv -1$, and determine whether the choice yields a non-trivial factor. What fraction of choices succeed?

Exercise 15.8 (Discrete Logarithm). Let $g = 2$ be a generator of $\mathbb{Z}_{11}^*$ and $h = g^x = 9$. Use the quantum discrete logarithm algorithm to find $x$. Set up the two-register state, identify the period, and show how the measurement reveals $x = 6$.

Exercise 15.9 (Resource Estimation). Estimate the number of physical qubits needed to factor a 1024-bit RSA integer using Shor's algorithm with the surface code. Assume: (a) logical qubits needed = $2 \times 1024 + 1024 + \text{ancilla} \approx 4000$, (b) surface code distance $d = 17$ (for logical error rate $10^{-15}$), (c) physical-to-logical qubit ratio = $2d^2 \approx 578$. What is the total physical qubit count?

Exercise 15.10 (Classical Post-Processing). Suppose Shor's algorithm on $N = 77$, $a = 2$ produces the measurement outcome $c = 21845$ with $t = 16$ qubits. (a) Compute $c/2^t$ and find its continued fraction expansion. (b) Identify the convergent that gives the period. (c) Verify by computing $a^r \bmod 77$. (d) Find the factors of 77.