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 o modulo . Zamiast sprawdzać, czy , 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$ $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)$

quantum-computing nt.number-theory factoring

— Frédéric Grosshans
źródło

Co robi algorytm? Zasadniczo bierze i losowe i wyprowadza . więc jeśli zaznaczysz wszystkie małe wielokrotności , jest bardzo prawdopodobne, że jest jednym z nich. Dlaczego podaje ? To teoria liczb. Andrew Odlyzko jest teoretykiem liczb i skonsultowałem się z nim w sprawie tego problemu, ale całkowicie zapomniałem o jego uzasadnieniu.

r

$r$

ℓ \leq r

$\ell \leq r$

r^{'} = r / g c d (ℓ, r)

$r' = r/gcd(\ell,r)$

r^{'}

$r'$

r

$r$

(\log n)^{1 + ϵ}

$(\log n)^{1+\epsilon}$

O (1)

$O(1)$

— Peter Shor,

Dzięki! Wygląda na to, że sam muszę poszukać teoretyka liczb!

— Frédéric Grosshans

Możesz wypróbować MathOverflow .

— Kaveh

Myślę nad tym. Prawdopodobnie przeformułuję to w bardziej „teoretyczny sposób”, jeśli wkrótce nie otrzymam odpowiedzi. Myślę, że można to sformułować jako sumę funkcji totalnych.

— Frédéric Grosshans

@Kaveh: Powiązane pytanie dotyczące MathOverflow , zadające powiązane pytanie teorii liczb, które moim zdaniem jest równoważne.

— Frédéric Grosshans