Chapter 9, Shor’s Algorithm
- We start by finding values of 3n % 14:
- We start by finding values of 2n % 35:
- Dividing 71 by 8 gives us 8 with a remainder of 7. So,
is the same as
. According to Figures 9.9 and 9.13,
is equal to
.
- The QFT and QFT† matrices are shown here:
- The 2 × 2 QFT matrix is the Hadamard matrix because the second roots of unity are 1 and -1.
- The missing values are shown here:
- In the coprime powers sequence for 22 (with coprime 3), the period is 5. But 5 isn’t divisible by 2. You can’t find 35/2 + 1 or 35/2 &...

Next, we calculate the following:
When we calculate 14/13, we find that it isn’t an integer. But 14/2 = 7. So, 14 = 2·7.

Next, we calculate the following:
When we calculate 35/13 and 35/3, we find that these aren’t integers. But 35/5 = 7. So, 35 = 5·7.
