O algoritimo de shor e sua aplicação na criptografia rsa

SUMÁRIO
INTRODUÇÂO 08
1 FATORAÇÃO E SEUS MÉTODOS 10
1.1 Divisibilidade 10
1.2 Números primos 11
1.3 Métodos de fatoração 12
1.3.1 Fatoração em números primos 12
1.3.2 Método de Fermat 13
2 MÁQUINAS DE TURING 17
2.1 Alan Turing 17
2.2 Máquinas de Turing 18
2.3 Tese de Church 21
2.3.1 Alonzo Church 21
2.3.2 A hipótese 21
2.4 Definição formal da Máquina de Turing 25
3 CRIPTOGRAFIA 34
3.1 A escrita secreta na antiguidade 34
3.2 Criptografia na história 35
3.3 Análise de frequência 39
3.4 Código 45
3.5 Alan Turing e a Máquina Enigma 46
4 O RSA 48
4.1 O RSA e suas aplicações 48
4.2 Chave pública e chave privada 48
4.3 Aplicando o código RSA 51
5 ALGORITMOS 58
6 MECÂNICA QUÂNTICA 77
6.1 A origem 77
6.2 Ondas de matéria 81
6.3 A equação de Schrödinger 83
6.4 O Gato de Schrödinger 85
6.5 Spin 87
7 COMPUTAÇÃO QUÂNTICA 89
7.1 Uma nova computação 89
7.2 Qubit 90
7.3 Dificuldades 93
7.4 Novos experimentos 95
8 O ALGORITMO DE SHOR 97
8.1 Peter Shor 97
8.2 O potencial do Algoritmo de Shor 98
8.3 O algoritmo 99
8.3.1 Redução à busca do período 100
8.3.2 Transformada Quântica de Fourier 102
8.3.3 A fatoração 103
8.4 Usando a programação quântica 105
8.5 O Algoritmo de Shor e a criptografia RSA 110
CONSIDERAÇÕES FINAIS 115
REFERÊNCIAS BIBLIOGRÁFICAS 117
LISTA DE ILUSTRAÇÕES
FIGURA 1 – Fatores da divisão 10
FIGURA 2 – Exemplos de fatoração 12
FIGURA 3 – Fita da Máquina de Turing 19
FIGURA 4 – Funcionamento de uma fita na Máquina de Turing 20
FIGURA 5 – Fita após ser processada na Máquina de Turing 21
FIGURA 6 – Tipos de problemas 22
FIGURA 7 – Problemas intermediários 24
FIGURA 8 – Universo de problemas em suas classes 24
FIGURA 9 – Exemplo formal de fita em uma Máquina de Turing 27
FIGURA 9.1 – Exemplo formal de fita em uma Máquina de Turing 28
FIGURA 9.2 – Exemplo formal de fita em uma Máquina de Turing 29
FIGURA 9.3 – Exemplo formal de fita em uma Máquina de Turing 30
FIGURA 9.4 – Exemplo formal de fita em uma Máquina de