Order finding becomes a factoring method only when a chosen base has a useful order. An even order alone is not enough: if its halfway power is modulo the number being factored, both gcd calculations are unhelpful. We prove that, once simple cases are removed, a uniformly random unit avoids these obstructions with probability at least one half. This is a classical probability statement assuming the exact order is supplied for every base; it is not the success probability of an entire quantum run.
The halfway power
Definition 2.6.1
(Order and halfway power)
For a unit modulo , is the least positive integer with . When is even, the halfway power of is .
Let be a positive odd integer with at least two distinct prime factors and let be chosen uniformly from . Write for the least positive integer with . If is even, put . Then , but by minimality of . If also , both
are nontrivial factors. Indeed ; if one gcd were 1, cancellation would make the other factor divisible by , contradicting the corresponding exclusion. Neither gcd is .
The random-base theorem
Theorem 2.6.2
(A useful order with probability at least one half)
For positive odd with at least two distinct prime factors, a uniformly random unit has even order and with probability at least .
Proof
(Compare powers of two in local orders)
Factor , where and the are distinct odd primes. The Chinese remainder theorem identifies a uniform unit modulo with independent uniform units modulo each . Put and , the exponent of 2 in . The global order is .
If all , then is odd. Otherwise set . At a component where , the integer is divisible by , so . At a component where , the element has order two. For an odd prime power the only roots of are and : the odd prime cannot divide both and . Since divides their product, it divides the one of these factors that is divisible by . Hence this local value is . Consequently the procedure fails exactly when all the are equal: all zero gives odd order, while a common positive value gives in every component. If they differ, has both and components and the gcds split .
It remains to bound the probability of equality. The group of units modulo an odd prime power is cyclic. If its order is with odd and , the fraction of elements whose order has 2-adic valuation is for , and for . Each probability is at most . This follows by counting elements of each order in the cyclic 2-primary factor; the odd factor has no effect on .
Independence now gives
The final sum is the probability that all match, interpreted as 1 when . Thus the useful event has probability at least .
Proof X-ray
Where each hypothesis enters
Three hypotheses carry the proof. Uniformity of over the units is what lets the Chinese remainder theorem make the local components independent, which is the only source of the product in the final estimate. Oddness of the primes makes each local unit group cyclic of even order, with exactly one element of order two, namely ; this is why a component with maximal contributes and every other component contributes . The condition is used in the last line: it supplies a factor multiplying a probability that is at most one. The non-obvious move is the reformulation: the procedure fails exactly when all are equal, which turns a question about into a question about 2-adic valuations of independent local orders. For the reformulation still holds but the bound does not, since a single is trivially equal to itself.
Worked example 2.6.3
(Different local orders split 21)
Take and . Modulo 3 the order is 2; modulo 7 it is 3. Hence and . The local signs are and , so and . By contrast has order 2 and gives , yielding only 1 and 21.
Worked example 2.6.4
(Counting every unit modulo 15)
There are units: , with orders . Base has odd order, and base has halfway power . For the halfway powers are , none of which is , so each of these six bases splits . The proportion of useful bases is .
Worked example 2.6.5
(Equal two-adic valuations)
Take and . Modulo the element has order , and modulo the element has order , so . Both components of equal , hence and the procedure fails, exactly as the criterion predicts.
Common mistake
(An even order is not enough)
An even order does not make useful: if , both gcds are trivial. For and the order is , but , so and .
Counterexample mode
An odd prime power has no useful base
A tempting claim is that the one-half bound holds for every odd . For the units are with orders . Bases have odd order. For the halfway powers are , and , all congruent to . So no base factors and the proportion of useful bases is , not at least . The hypothesis of two distinct prime factors cannot be dropped, which is why prime powers are handled separately.
What this bound does and does not count
An implementation may first draw an integer from and compute its gcd with . A nontrivial gcd already factors ; conditional on gcd 1, the draw is uniform among units, as required above. Even inputs and prime powers are handled separately; the theorem deliberately excludes an odd prime power because a nontrivial square root of 1 need not exist there. A quantum order-finding measurement followed by classical reconstruction may yield only a divisor of the order or an inaccurate candidate. Reconstructing and verifying candidates, and bounding the cost and probability of obtaining the exact order, are additional steps; multiplying the above by a claimed quantum success rate requires justifying that rate and the conditioning.
Practice and solutions
Quick check
(For and , find , its halfway power and the resulting gcds.)
Solution · Answer
, ; the gcds are and .
Quick check
(Explain why fails for despite having even order.)
Solution · Answer
The order is but , so the gcds are and . The theorem promises a probability over bases, not success for every base.
Quick check
(For and , find the order, the halfway power and the factors obtained.)
Solution · Answer
Modulo the order is and modulo it is , so . Then , which is modulo and modulo . Hence and .