# Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

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?

• What does the algorithm do? Essentially, it takes $r$ and a random $\ell \leq r$ and outputs $r' = r/gcd(\ell,r)$. so if you check all small multiples of $r'$, then it is very likely that $r$ is one of these. Why does $(\log n)^{1+\epsilon}$ give $O(1)$? That's number theory. Andrew Odlyzko is a number theorist, and I consulted him about this problem, but I've completely forgotten his justification for this. Jul 26 '15 at 16:39
• Thanks! It looks like I need to look for a number theorist myself! Jul 27 '15 at 6:16
• You may want to try MathOverflow. Jul 27 '15 at 18:06
• I’m thinking about it. I will probably reformulate it in a more “number theoretic way” for that, if I don’t get the answer soon. I think it can be rephrased as a sum of totient functions. Jul 27 '15 at 18:20
• @Kaveh : The related question on MathOverflow, asking a related number theory question which, I think, is equivalent. Jul 31 '15 at 15:51