Algoritmo de Shor: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 7:
| eprint = 0808.0369
}}</ref> para fatorar um número ''N'' não [[Número primo|primo]] de ''L'' bits<ref>[http://katzgraber.org/teaching/fs08/files/herrigel.pdf| Shor’s Algorithm] por Roger Herrigel e Wojciech De Roeck em 14 de abril de 2008</ref>.
Usando bits quânticos, ou [[qubit]]s reciclados, o cálculo quântico de Shor é utilizado, explorando a [[mecânica quântica]], para simplificar a fatoração de números em seus componentes principais - uma tarefa difícil para os computadores comuns, clássico, quando os números ficam muito grande. Até 2012, o maior número fatorado usando o algoritmo de Shor era 15.<ref>[http://www.newscientist.com/article/mg21628885.400-recycled-photons-set-fresh-quantum-computing-record.html#.VM3IfGjF98E|Recycled photons set fresh quantum computing record] por Jacob Aron em 23 de outubro de 2012</ref>
==Descrição==
Definir o período de uma função não é simples, mas encontrar o período de uma função relacionada com o número 15 pode ser descrita da seguinte forma:
*Em primeiro lugar, encontre um número que não tem fatores em comum com 15, diferente de 1. Por Exemplo, você escolhe 11.
*Então:
*Divida 11 por 15 para obter 0, com um resto de 11.
*Eleve ao quadrado o restante, encontrando 121.
*Divida 121 por 15 para obter 8 com um resto de 1.
*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 para poderes superiores, vamos notar uma coisa curiosa sobre o resto quando dividimos por 15: ele irá 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ê elevar 11 para o poder dado pelo seu período, que é 2, a resposta é 121.
*Agora, tire a raiz quadrada para obter 11.
*O próximo passo envolve a adição de 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 verdadeiramente enormes números, 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.
==Referências==
<references/>
| |||