¿Por qué la mejora de Odlyzko del algoritmo de Shor reduce el número de ensayos a

En su artículo de 1995 Algoritmos de tiempo polinómico para la factorización prima y los logaritmos discretos en una computadora cuántica , Peter W. Shor analiza una mejora en la parte de búsqueda de orden de su algoritmo de factorización. Las salidas algoritmo estándar $r'$ , un divisor de la orden $r$ de $x$ modulo $N$ . En lugar de comprobar si $r'=r$ comprobando si $x^{r'}\equiv 1 \mod N$ , la mejora es la siguiente:

[F] o un candidato uno debe considerar no solo sino también sus pequeños múltiplos , para ver si estos son el orden real de . [... Esta] técnica reducirá el número esperado de pruebas para el más difícil de a si los primeros ( múltiplos de Se consideran [Odylzko 1995]. $r$ $r ′$ $2r ′ , 3r ′ , \dots$ $x$ $n$ $O(\log \log n)$ $O(1)$ $\log n)^{1+\epsilon}$ $r ′$

La referencia a [Odylzko 1995] es una "comunicación personal", pero no estaba presente cuando Peter Shor y Andrew Odlyzko discutieron esto ... Entiendo perfectamente por qué es una mejora, pero no sé cómo mostrar el número de ensayos se reduce a . ¿Conoces alguna prueba de esto? $O(1)$

quantum-computing nt.number-theory factoring Frédéric Grosshans
fuente

¿Qué hace el algoritmo? Esencialmente, toma y un aleatorio y genera . así que si marca todos los pequeños múltiplos de , entonces es muy probable que sea uno de estos. ¿Por qué da ? Esa es la teoría de números. Andrew Odlyzko es un teórico de números, y lo consulté sobre este problema, pero he olvidado por completo su justificación.

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

¡Gracias! ¡Parece que necesito buscar un teórico de números yo mismo!

Frédéric Grosshans

Es posible que desee probar MathOverflow .

Kaveh

Estoy pensando en ello. Probablemente lo reformule de una manera más "teórica de números" para eso, si no obtengo la respuesta pronto. Creo que puede reformularse como una suma de funciones totient.

Frédéric Grosshans

@Kaveh: La pregunta relacionada en MathOverflow , haciendo una pregunta relacionada con la teoría de números que, creo, es equivalente.

Frédéric Grosshans

¿Por qué la mejora de Odlyzko del algoritmo de Shor reduce el número de ensayos a

Respuestas: