Phase estimation hands you a decimal. How does that become the period Shor's algorithm needs?
Simon's algorithm (topic 10) found a hidden XOR-period using n Hadamard gates and ordinary linear algebra, because XOR-periods live in the group (ℤ/2ℤ)ⁿ and the Hadamard transform is exactly the Fourier transform over that group. Real periods (the ones behind factoring) live in ℤ/2tℤ instead, a bigger, different group, and finding them needs the Fourier transform for that group: the quantum Fourier transform. These three topics build it, use it to read out an unknown phase, and use that to recover a period: the exact chain Shor's algorithm runs, derived here instead of asserted there.
Here is the step the figure above takes for granted. After the machine measures the second register, the counting register holds an even spread over every x that is one period apart. The Fourier transform then makes the chance of each outcome k the squared length of a sum of one little arrow per x. Where the arrows line up the sum is long and k is likely; everywhere else they curl round and cancel. Pick a number, look at any k, or run the whole thing and let the continued-fraction step try to recover the period.
Honest limits: this is a classical simulation of the quantum state, exact for these small numbers, and it costs memory that doubles with every counting qubit, which is why a quantum computer is needed for a 2,048-bit N. It shows the mechanism, not the speed. Runs that fail are not a flaw in the drawing: topic 13 explains why a shared factor between the measured numerator and the period makes the first try return only a divisor of it.
Shor's algorithm needs the period r of f(x) = ax mod N for a random a coprime to N: the smallest r with ar ≡ 1 (mod N). The unitary U|y⟩ = |ay mod N⟩ has eigenvalues e2πis/r for integers s=0,...,r−1, so phase estimation (topic 12), run on U, returns an estimate of θ=s/r for some s you don't get to choose.
Phase estimation hands back a t-bit number m/2t, close to the true θ=s/r but not equal to it. Turning "a decimal close to s/r" back into "the integer r" is exactly the job of an ancient classical algorithm: the continued fraction expansion, which finds the simplest fraction close to any given number. Feed it the measured m/2t, ask for fractions with denominator under N, and (when the measurement was accurate enough and s happens to share no common factor with r) the true r pops out as one of the expansion's convergents.
The subtlety that makes this genuinely probabilistic, not deterministic: s is effectively a random integer in {0,..., r−1}, and if gcd(s, r) > 1, the fraction s/r reduces before the continued-fraction algorithm ever sees it: what comes back is r/gcd(s, r), a real divisor of r, not r itself. This isn't a bug or an approximation error; it's what the fraction s/r actually equals once reduced. The fix, standard in every real implementation, is to repeat the whole phase-estimation-plus-continued-fraction pipeline a handful of times and take the least common multiple of whatever comes back: enough repeats make the true r appear with overwhelming probability, since a s coprime to r turns up often enough in practice to make this a small, bounded number of retries rather than a real bottleneck.
The classical guarantee. If θ is within 1/(2r²) of some fraction s/r in lowest terms with r < N, then s/r is guaranteed to appear as a convergent of θ's continued fraction expansion (a number-theoretic fact independent of quantum mechanics) Legendre's theorem on continued-fraction convergents (Legendre, Essai sur la théorie des nombres, 1798). Choosing t ≈ 2 log₂N counting qubits in phase estimation makes the measured m/2t land within this radius of the true s/r, satisfying the guarantee's hypothesis.
What the guarantee does and doesn't promise: it promises s/r appears as a convergent: the fraction actually equal to the measured phase in lowest terms. When gcd(s, r)=1, that fraction's denominator is r. When gcd(s, r)=g>1, the reduced fraction's denominator is r/g: a proper divisor, and the guarantee still holds exactly, just for a smaller number.
Verified numerically over 2,000 random (N, r, s) triples with t = 2·⌈log₂N⌉ counting qubits, using the ideal (noiseless) measurement outcome m = round(s/r·2t): every one of the 1,189 trials with gcd(s, r)=1 recovered r exactly as a convergent denominator (1,189/1,189); every one of the 811 trials with gcd(s, r)>1 recovered exactly r/gcd(s, r) as predicted, never r itself and never a wrong answer (811/811). Shor, SIAM J. Comput. 26(5), 1484 (1997; FOCS 1994); continued-fraction period recovery: Nielsen & Chuang, Quantum Computation and Quantum Information, §5.3.1.
The step that makes Shor's algorithm actually run This is the last link in the chain this section built: topic 11's transform, run inside topic 12's phase estimation, applied here to modular multiplication, turns "factor N" into "find a period," exactly as the Shor estimator asserts without deriving. The parallel to topic 10 is exact and deliberate: Simon's algorithm solves the identical shape of problem (recover a hidden period) over the group (ℤ/2ℤ)ⁿ using the Hadamard transform; this section solves it over ℤ/2tℤ using the full QFT. Same idea, generalised from the smallest possible group to the one factoring actually needs.
Check yourself
The continued-fraction step sometimes returns r divided by gcd(s, r) instead of the period r. What do real implementations do about it?
It is not an error: s/r reduces before the continued-fraction algorithm sees it. Repeating and taking the lcm makes the true r appear with overwhelming probability.