Por que a melhoria Odlyzko do algoritmo de Shor reduz o número de tentativas para

19

Em seu artigo de 1995, Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico , Peter W. Shor discute uma melhoria na parte de busca de pedidos de seu algoritmo de fatoração. As saídas algoritmo padrão , um divisor de ordem de módulo . Em vez de verificar se verificando se , a melhoria é a seguinte: r x N r = rrrxNr=rxr1modN

[F] ou um candidato r deve considerar não apenas r mas também seus pequenos pequenos 2r,3r, , para ver se essa é a ordem real de x . [...] essa técnica reduzirá o número esperado de tentativas para o n mais difícil nde O(loglogn) para O(1) se o primeiro ( logn)1+ϵ múltiplos de r São considerados [Odylzko 1995].

A referência a [Odylzko 1995] é uma "comunicação pessoal", mas eu não estava presente quando Peter Shor e Andrew Odlyzko discutiram isso ... Eu entendo perfeitamente por que é uma melhoria, mas não sei como mostrar o número dos ensaios é reduzido para O(1) . Você conhece alguma prova disso?

Frédéric Grosshans
fonte
7
O que o algoritmo faz? Essencialmente, é necessário r e um \ ell \ leq r aleatório re gera r=r/gcd(,r) . portanto, se você marcar todos os pequenos múltiplos de r , é muito provável que r seja um deles. Por que (logn)1+ϵ fornece O(1) ? Essa é a teoria dos números. Andrew Odlyzko é um teórico dos números e eu o consultei sobre esse problema, mas esqueci completamente sua justificativa para isso.
266 Peter Shor Shor
Obrigado! Parece que eu preciso procurar um teórico dos números!
Frédéric Grosshans
Você pode tentar o MathOverflow .
Kaveh
Estou pensando sobre isso. Provavelmente vou reformular isso de uma maneira mais "teórica dos números" para isso, se não receber a resposta em breve. Eu acho que pode ser reformulado como uma soma de funções totientes.
Frédéric Grosshans
2
@ Kaveh: A pergunta relacionada no MathOverflow , fazendo uma pergunta relacionada à teoria dos números, que eu acho que é equivalente.
Frédéric Grosshans

Respostas: