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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.