Dlaczego poprawa algorytmu Shora przez Odlyzko zmniejsza liczbę prób do

W swoim artykule z 1995 r. „ Algorytmy czasowe wielomianowe dla faktoryzacji pierwotnej i logarytmów dyskretnych na komputerze kwantowym” Peter W. Shor omawia ulepszenie części algorytmu faktoryzacji polegającej na ustalaniu kolejności. Standardowe wyjścia algorytm , dzielnik w kolejności R o x modulo N . Zamiast sprawdzać, czy r ′ = r , sprawdzając, czy , poprawa jest następująca:$r'$$r$$x$$N$$r'=r$$x^{r'}\equiv 1 \mod N$

[F] lub kandydat należy wziąć pod uwagę nie tylko ale także jego małe wielokrotności , aby sprawdzić, czy jest to rzeczywista kolejność . [... Ta] technika zmniejszy oczekiwaną liczbę prób dla najtwardszego od do jeśli pierwsza ( wielokrotność Są uważane za [Odylzko 1995].r ′ 2 r ′ , 3 r ′ , … x n O ( log log n ) O ( 1 ) log n ) 1 + ϵ r $r$$r ′$$2r ′ , 3r ′ , \dots$$x$$n$$O(\log \log n)$$O(1)$$\log n)^{1+\epsilon}$$r ′$

Odniesienie do [Odylzko 1995] jest „osobistą komunikacją”, ale nie byłem obecny, gdy Peter Shor i Andrew Odlyzko rozmawiali o tym ... Doskonale rozumiem, dlaczego jest to poprawa, ale nie wiem, jak pokazać liczbę prób jest zredukowany do . Czy znasz na to jakiś dowód?$O(1)$

Odpowiedź Terry'ego Tao na MathOverflow.