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?

  • 7
    $\begingroup$ 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. $\endgroup$ Jul 26 '15 at 16:39
  • $\begingroup$ Thanks! It looks like I need to look for a number theorist myself! $\endgroup$ Jul 27 '15 at 6:16
  • $\begingroup$ You may want to try MathOverflow. $\endgroup$
    – Kaveh
    Jul 27 '15 at 18:06
  • $\begingroup$ 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. $\endgroup$ Jul 27 '15 at 18:20
  • 2
    $\begingroup$ @Kaveh : The related question on MathOverflow, asking a related number theory question which, I think, is equivalent. $\endgroup$ Jul 31 '15 at 15:51

Terry Tao's answer on MathOverflow.


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .