An order-finding circuit does not print the order directly. It can produce a measurement close to a fraction whose reduced denominator divides the order. Classical post-processing must recover a candidate, check what it means, and sometimes discard the result. The distinction between a period and the least period is essential when the candidate is used for factoring.
The order as an eigenphase
Definition 2.7.1
(Order and the multiplication unitary)
Let and with . The order is the least positive integer such that . It exists because multiplication by permutes residues modulo ; in particular . On a register whose basis contains the residues, define for and let it fix unused basis states. This is unitary.
Definition 2.7.2
(Eigenstates of the multiplication unitary)
The orbit has distinct elements. For , define
Shifting the index cyclically gives . The form an orthonormal basis of the orbit subspace, and Fourier orthogonality gives
Thus a phase-estimation experiment starting with has the same measurement distribution as first choosing uniformly from and then estimating . This conceptual mixture follows from orthogonality of the eigenstates; the circuit need not measure .
Precision and the fraction to reconstruct
Choose a control-register size with . For a fixed , let be a nearest integer to , with a fixed tie rule. It lies in , and ideal phase estimation returns this particular with probability at least . The nearest-grid bound follows from its geometric-sum distribution: if , then , with the exact-grid case having probability one. There is no wraparound ambiguity here: for , while the grid spacing is much smaller.
On this favorable event,
Reduce to in lowest terms. Then , where . Consequently and the same error is strictly less than .
We invoke the classical continued-fraction approximation theorem: if a reduced rational satisfies , it is a convergent of the simple continued fraction of . Thus appears among the convergents of the measured rational . The theorem is cited here, not proved. Euclid's algorithm computes these convergents; its finite rational expansion can be processed exactly without floating-point rounding.
Proposition 2.7.3
(A bounded fraction close to is unique)
Fix integers and . At most one reduced fraction with satisfies .
Proof
(Distinct fractions are far apart)
Let be two reduced fractions with . Then , because is a nonzero integer. If both fractions were strictly within of , the triangle inequality would give , a contradiction.
This uniqueness is an error guarantee, not a way to know from a single sample that the favorable event occurred.
Common mistake
(Reading the reduced denominator as the order)
The observed fraction is , but the continued fraction reveals it in lowest terms. If and share a factor, its denominator is a proper divisor of . The zero phase gives denominator 1 regardless of the order. A precise phase estimate is therefore not automatically an order estimate.
Verification and its limits
Compute convergents with denominators at most and test each denominator by modular exponentiation: does ? Any passing is a period, but need not be the least one.
Proposition 2.7.4
(Order recovery from a coprime sample)
Suppose and with and . Then occurs as a convergent denominator at most , every passing denominator is a multiple of , and the smallest passing denominator among the tested convergents is .
Proof
(Periods are multiples of the order)
Because , the reduced form of has denominator , and it appears among the convergents by the approximation theorem. If , write with ; then , and minimality of forces . So every passing period is a multiple of , hence at least , and itself passes.
The probability of this sufficient event is at least
where counts residues coprime to , with . This lower bound combines the uniform choice of with the nearest-grid guarantee. Other samples might also lead to the correct order. The expression depends on ; it is not a uniform constant lower bound from this calculation alone. Repetition and further analysis are needed for an overall factoring algorithm.
Counterexample mode
A passing exponent need not be the order
For and , the order is . A sample of phase has reduced denominator 2, but , so testing rejects it as a period. Conversely, passes because , yet it is not the least period. Every passing denominator is a multiple of , but it need not equal .
Worked example 2.7.5
(Reading the order from an exact grid sample)
With , , take . A nearest-grid result gives , already reduced. Its denominator passes . Here is coprime to 4, so the favorable-event argument identifies the order as 4. The outcome instead yields and the rejected denominator 2. This exact example does not require every phase to be exactly representable for other orders.
Worked example 2.7.6
(A sample that is not on the grid)
Let and . The powers show that the order is . Take . For we have , so and , which is not exactly . The Euclidean algorithm gives , , , so the continued fraction is with convergents . The denominators at most are . Testing , and , the smallest passing denominator is . Finally , and , .
Worked example 2.7.7
(A sample whose denominator has shrunk)
Keep , , , and take . Then , so and . Since , the continued fraction is with convergents , , . The denominators at most are and , and , are not modulo . The test rejects both, correctly: , so the reduced phase is , whose denominator is a proper divisor of . This run is discarded and repeated.
From a period to factors
Proposition 2.7.8
(Factors from a nontrivial square root of one)
Let be an even period, so , and let . If and , then and
Proof
(Canceling a coprime factor)
Indeed , so divides , while neither factor is divisible by . If , cancellation modulo would force , contrary to the hypothesis; similarly the other gcd exceeds 1. Neither equals . Thus either gcd gives a nontrivial factor. This criterion works for any verified even period with the displayed nontrivial-square-root test; it need not first prove minimality.
Proof X-ray
Where the square-root test is used
The congruence comes from being an even period. The conditions and say that divides neither nor , while it divides their product, so is shared between the two factors. The one non-obvious move is the cancellation step: a factor coprime to is invertible modulo , which turns “gcd equals 1” into the forbidden congruence. For composite there are square roots of other than ; modulo they are and , and these are exactly the values that produce factors. No minimality of is used.
For , , the order 4 gives , hence and . The passing period 8 instead gives , so it fails the square-root test and yields no factors. Odd orders, trivial square roots, inaccurate phase samples and noncoprime all require separate handling or repetition. This calculation does not prove the success probability of choosing a random base or a complete factoring complexity theorem.
Practice with solutions
Quick check
(If and , what denominator appears after reducing ?)
Solution · Answer
, so the denominator is .
Quick check
(Why does alone not prove is the order?)
Solution · Answer
Every positive multiple of the order is also a period; for base modulo is an example.
Quick check
(For , , test and compute the resulting gcds.)
Solution · Answer
, and gives and .
Quick check
(What additional condition makes the reduced phase denominator equal to ?)
Solution · Answer
. The phase must also be recovered accurately for the conclusion to apply to a measured denominator.