<p><a href="https://mathoverflow.net/a/212754/7507">Terry Tao's answer</a> on MathOverflow.</p>

CC BY-SA 3.0
2015-07-31T20:13:30.297Z
2015-07-31T20:13:30.297Z
2017-04-13T12:57:54.777Z
Kaveh
<p>In his 1995 paper <a href="http://arxiv.org/abs/quant-ph/9508027" rel="noreferrer">Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer</a>, 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 : </p>

<blockquote>
  <p>[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].</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2015-07-26T16:39:31.697Z
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.
Peter Shor 
CC BY-SA 3.0
2015-07-27T06:16:40.127Z
Thanks! It looks like I need to look for a number theorist myself!
Frédéric Grosshans
CC BY-SA 3.0
2015-07-27T18:06:49.570Z
You may want to try [mathoverflow.se].
Kaveh
CC BY-SA 3.0
2015-07-27T18:20:36.513Z
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.
Frédéric Grosshans
CC BY-SA 3.0
2015-07-31T15:51:45.287Z
@Kaveh : The [related question on MathOverflow](http://mathoverflow.net/q/212741/4780), asking a related number theory question which, I think, is equivalent.
Frédéric Grosshans
<quantum-computing><nt.number-theory><factoring>
Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$
Frédéric Grosshans
# Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

(Asked by: username_0 on 2015-07-24)

In his 1995 paper [Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer](http://arxiv.org/abs/quant-ph/9508027), 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 username_1and 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?

**Tags:** quantum-computing, nt.number-theory, factoring

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks! It looks like I need to look for a number theorist myself!  
> **username_2**: You may want to try [mathoverflow.se].  
> **username_0**: 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.  
> **username_0**: @username_2 : The [related question on MathOverflow](http://mathoverflow.net/q/212741/4780), asking a related number theory question which, I think, is equivalent.  

---

## 1 answers

### Answer by username_2 on 2015-07-31. Score: 5

[Terry Tao's answer](https://mathoverflow.net/a/212754/7507) on MathOverflow.


---

