Wikipédia

Algoritmo de Shor: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m Ref
Trechos estavam mal escritos, parecendo tradução literal do inglês. Modifiquei o texto pra melhorar o entendimento e a fluidez.
Linha 18:
*Eleve ao cubo 11 para obter 1331.
*Divida 1331 por 15, para obter 88 com um resto de 11.
Se proceder desta forma, elevando 11 paraa poderespotências superiores, vamos notar umaalgo coisa curiosacurioso sobre o resto quando dividimos por 15: ele iráserá alternadamente vai ser 11 ou 1. Assim, dizemos que o período de 11 em relação a ser dividido por 15 é 2.
Isso é útil para fatorar 15, porque se você elevarelevarmos 11 para oà poderpotência dadodada pelo seu período, que é 2, a resposta é 121.
*Agora, tire a raiz quadrada para obter 11.
*O próximo passo envolve asubtrair adiçãoe desomar 1 a 11 e subtraia 1 de 11 para obter um par de números, 10 e 12.
*Encontre o maior denominador comum de 10 e 15, e 12 e 15. O primeiro é 5 e o último é 3, que são também os fatores de 15.
 
Com certeza, esse procedimento é ridiculamente longo para um problema tão trivial.
Mas quando ele é usado em números verdadeiramente enormes númerosgrandes, o procedimento é bastante eficiente. E para os grandes números usados na [[RSA]], levaria muito tempo, mesmo em um computador digital rápido, mas para um computador quântico é, relativamente, um piscar de olhos<ref>[http://www.newscientist.com/blog/technology/2007/09/how-quantum-computer-factorises-numbers.html| How a quantum computer factorises numbers] por Saswato Das em 2001</ref>.
 
 
Obtida de "https://pt.wikipedia.org/wiki/Algoritmo_de_Shor"