  We prove a lower bound on the probability of Shor's order-finding algorithm
successfully recovering the order $r$ in a single run. The bound implies that
by performing two limited searches in the classical post-processing part of the
algorithm, a high success probability can be guaranteed, for any $r$, without
re-running the quantum part or increasing the exponent length compared to Shor.
Asymptotically, in the limit as $r$ tends to infinity, the probability of
successfully recovering $r$ in a single run tends to one. Already for moderate
$r$, a high success probability exceeding e.g. $1 - 10^{-4}$ can be guaranteed.
As corollaries, we prove analogous results for the probability of completely
factoring any integer $N$ in a single run of the order-finding algorithm.
