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

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2338 palavras )
  • Download(s) : 0
  • Publicado : 17 de maio de 2012
Ler documento completo
Amostra do texto
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 343.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 Gatode 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.5O 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 22FIGURA 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 deTuring 31
FIGURA 9.5 – Exemplo formal de fita em uma Máquina de Turing 32
FIGURA 10 – Transposição cerca de ferrovia de duas linhas 37
FIGURA 11 – Criptografia sugerida pelo Kama-Sutra 37
FIGURA 12 – Cifra de César 38
FIGURA 13 – Fluxo de criptografia 38
FIGURA 14 – Mensagem criptografada monoalfabética 41
FIGURA 15 – Descobrindo algumas letras do texto cifrado 43
FIGURA 16 – Desvendandomais letras do texto cifrado 44
FIGURA 17 – Texto original 45
FIGURA 18 – Código 46
FIGURA 19 – A ciência da escrita secreta e suas ramificações 46
FIGURA 20 – Alice e Bob – comunicação entre chaves 50
FIGURA 21 – Divisibilidade em JAVA 58
FIGURA 21.1 – Colocando o valor do dividendo 10 59
FIGURA 21.2 – Colocando o valor do divisor 5 59
FIGURA 21.3 – Mostrando a divisibilidade entre odividendo 10 e o
divisor 5 59
FIGURA 21.4 – Colocando o valor do dividendo 15 59
FIGURA 21.5 – Colocando o valor do divisor 7 60
FIGURA 21.6 – Mostrando a divisibilidade entre o dividendo 15 e o
divisor 7 60
FIGURA 22 – Primalidade em JAVA 61
FIGURA 22.1 – Verificando a primalidade do número 8 61
FIGURA 22.2 – Primalidade do número 8 61
FIGURA 22.3 – Verificando a primalidade do número 23 62FIGURA 22.4 – Primalidade do número 23 62
FIGURA 23 – Fatoração em JAVA 63
FIGURA 23.1 – Fatoração em JAVA 64
FIGURA 23.2 – Fatoração em JAVA 65
FIGURA 23.3 – Inserindo o número 23 66
FIGURA 23.4 – Mostrando que o número 23 é primo e não haverá
fatoração 66
FIGURA 23.5 – Inserindo o número 20 66
FIGURA 23.6 – Mostrando a fatoração do número 20 66
FIGURA 23.7 – Inserindo o número 200.00066
FIGURA 23.8 – Mostrando a fatoração do numero 200.000 67
FIGURA 24 – Método de fatoração por Fermat em JAVA 68
FIGURA 24.1 – Inserindo o número 369852 68
FIGURA 24.2 – Mostrando a fatoração por Fermat do
número 369852 68
FIGURA 24.3 – Inserindo o número 345 69
FIGURA 24.4 – Mostrando a fatoração por Fermat do número 345 69
FIGURA 25 – O algoritmo RSA em JAVA 70
FIGURA 25.1 – O...
tracking img