Pourquoi l'amélioration d'Odlyzko de l'algorithme de Shor réduit le nombre d'essais à

Dans son article de 1995 Algorithmes à temps polynomial pour la factorisation principale et les logarithmes discrets sur un ordinateur quantique , Peter W. Shor discute d'une amélioration de la partie recherche d'ordres de son algorithme de factorisation. Les sorties algorithme standard , un diviseur de l'ordre de modulo . Au lieu de vérifier si en vérifiant si , l'amélioration est la suivante: $r'$ $r$ $x$ $N$ $r'=r$ $x^{r'}\equiv 1 \mod N$

[F] ou un candidat on devrait considérer non seulement mais aussi ses petits multiples , pour voir s'ils sont de l'ordre réel de . [... Cette] technique réduira le nombre prévu d'essais pour les les plus difficiles de à si les premiers ( multiples de Sont considérés [Odylzko 1995]. $r$ $r ′$ $2r ′ , 3r ′ , \dots$ $x$ $n$ $O(\log \log n)$ $O(1)$ $\log n)^{1+\epsilon}$ $r ′$

La référence à [Odylzko 1995] est une "communication personnelle", mais je n'étais pas présent lorsque Peter Shor et Andrew Odlyzko en ont discuté ... Je comprends parfaitement pourquoi c'est une amélioration, mais je ne sais pas comment montrer le nombre des essais est réduit à . Connaissez-vous une preuve de cela? $O(1)$

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

Que fait l'algorithme? Essentiellement, il prend et un aléatoire et sort . donc si vous cochez tous les petits multiples de , alors il est très probable que soit un. Pourquoi donne-t-il ? C'est la théorie des nombres. Andrew Odlyzko est un théoricien des nombres, et je l'ai consulté à propos de ce problème, mais j'ai complètement oublié sa justification.

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

Merci! Il semble que je doive chercher moi-même un théoricien des nombres!

Frédéric Grosshans

Vous voudrez peut-être essayer MathOverflow .

Kaveh

J'y pense. Je vais probablement le reformuler d'une manière plus «théorique des nombres» pour cela, si je n'obtiens pas la réponse bientôt. Je pense qu'il peut être reformulé comme une somme de fonctions totientes.

Frédéric Grosshans

@Kaveh: La question connexe sur MathOverflow , posant une question relative à la théorie des nombres qui, je pense, est équivalente.

Frédéric Grosshans

Pourquoi l'amélioration d'Odlyzko de l'algorithme de Shor réduit le nombre d'essais à

Réponses: