Por que a complexidade computacional da fatoração de números inteiros é exp(raiz(N))?

Computação e Informação Quântica

Fatorar um número inteiro significa encontrar os fatores primos deste.

Exemplos: 15 = 3*5, ou 187 = 11*17

A fatoração tem duas características: é difícil de fazer, mas é fácil de checar se uma solução é válida.

Exemplo: Quais os fatores primos de 3127?

Um método possível para encontrar os fatores do número N é testar todas as alternativas até raiz(N). Ou seja, dividir 3127 por 2, 3, 5, 7, 9, até raiz(3127) ~= 55.

Com isso, chegamos que 3127 = 53*59. E é fácil checar que 59 é um dos fatores de 3127, basta fazer a divisão.

A fatoração de números inteiros (ou melhor, a dificuldade em fazê-lo) é a base de toda a criptografia moderna.

O número grande (digamos 3127) é a minha chave pública com a qual o emissor da informação faz a codificação. Para decodificar, preciso da chave privada (53 e 59). E a segurança baseia-se…

Ver o post original 476 mais palavras

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s