In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his factorization algorithm. The standard algorithm outputs $r'$, a divisor of the order $r$ of $x$ modulo $N$. Instead of checking if $r'=r$ by checking if $x^{r'}\equiv 1 \mod N$, the improvement is the following :
[F]or a candidate $r$ one should consider not only $r ′$ but also its small multiples $2r ′ , 3r ′ , \dots$ , to see if these are the actual order of $x$. [... This] technique will reduce the expected number of trials for the hardest $n$ from $O(\log \log n)$ to $O(1)$ if the first ($\log n)^{1+\epsilon}$ multiples of $r ′$ are considered [Odylzko 1995].
The reference to [Odylzko 1995] is a “personal communication”, but I was not present when Peter Shor and Andrew Odlyzko discussed this... I perfectly understand why it is an improvement, but I don't know how to show the number of trials is reduced to $O(1)$. Do you know any proof of this?
