Por que a melhoria Odlyzko do algoritmo de Shor reduz o número de tentativas para

Em seu artigo de 1995, Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico , Peter W. Shor discute uma melhoria na parte de busca de pedidos de seu algoritmo de fatoração. As saídas algoritmo padrão , um divisor de ordem de módulo . Em vez de verificar se verificando se , a melhoria é a seguinte: r x N r ′ = $r'$$r$$x$$N$$r'=r$$x^{r'}\equiv 1 \mod N$

[F] ou um candidato $r$ deve considerar não apenas $r ′$ mas também seus pequenos pequenos $2r ′ , 3r ′ , \dots$ , para ver se essa é a ordem real de $x$ . [...] essa técnica reduzirá o número esperado de tentativas para o n mais difícil $n$de $O(\log \log n)$ para $O(1)$ se o primeiro ( $\log n)^{1+\epsilon}$ múltiplos de $r ′$ São considerados [Odylzko 1995].

A referência a [Odylzko 1995] é uma "comunicação pessoal", mas eu não estava presente quando Peter Shor e Andrew Odlyzko discutiram isso ... Eu entendo perfeitamente por que é uma melhoria, mas não sei como mostrar o número dos ensaios é reduzido para $O(1)$ . Você conhece alguma prova disso?

Resposta de Terry Tao no MathOverflow.