Algoritmo de Shor

Na teoria da complexidade computacional e em Computação quântica, o algoritmo de Shor, batizado em homenagem ao matemático Peter Shor, é um algoritmo quântico para fatorar um número N não primo de L bits.

Usando bits quânticos, ou qubits reciclados, o cálculo quântico de Shor é utilizado, explorando a mecânica quântica, para simplificar a fatoração de números em um produto de números primos - uma tarefa difícil para os computadores comuns, clássico, quando os números ficam muito grandes. Até 2012, o maior número fatorado usando o algoritmo de Shor era 15.

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 a potências superiores, vamos notar algo curioso sobre o resto quando dividimos por 15: ele será alternadamente 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 elevarmos 11 à potência dada pelo seu período, que é 2, a resposta é 121.

• Agora, tire a raiz quadrada para obter 11.
• O próximo passo envolve subtrair e somar 1 a 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 é demasiadamente longo para um problema trivial. Mas quando ele é usado em números verdadeiramente grandes, o procedimento é eficiente. Para os grandes números usados no algoritmo de criptografia de chave pública RSA, algoritmos clássicos para este problema levariam muito tempo para encontrar uma solução, mesmo utilizando computadores muito potentes. Entretanto, um computador quântico seria capaz de encontrar uma solução em tempo polinomial.