Почему улучшение алгоритма Шора в Odlyzko уменьшает количество испытаний до

В своей статье 1995 года « Алгоритмы полиномиального времени для первичной факторизации и дискретных логарифмов на квантовом компьютере» Питер У. Шор обсуждает усовершенствование порядка упорядочения своего алгоритма факторизации. Стандартные выходы алгоритма $r'$ , делитель порядка $r$ из $x$ по модулю $N$ . Вместо проверки, если $r'=r$ путем проверки, если , улучшение заключается в следующем:$x^{r'}\equiv 1 \mod N$

[F] или кандидата следует рассмотреть не только но и его малые кратные , чтобы увидеть, являются ли они действительным порядком . [... Этот] метод уменьшит ожидаемое число испытаний для самых сложных с до если первый ( кратен Считаются [Odylzko 1995].$r$$r ′$$2r ′ , 3r ′ , \dots$$x$$n$$O(\log \log n)$$O(1)$$\log n)^{1+\epsilon}$$r ′$

Ссылка на [Odylzko 1995] - это «личное общение», но я не присутствовал, когда Питер Шор и Андрей Одлызко обсуждали это ... Я прекрасно понимаю, почему это улучшение, но я не знаю, как показать число испытаний сводится к . Вы знаете какие-либо доказательства этого?$O(1)$

Ответ Терри Тао на MathOverflow.