Complexibilidade computacional no cálculo de números primos e perfeitos

Abstract

Fatorar um número de 12 milhões de dígitos ou confirmar sua primalidade não é trivial. Os números primos são conhecidos e estudados há séculos por cientistas e pesquisadores de diversas áreas, que dedicam suas vidas para desvendar alguma particularidade desta classe de números tão singular. Com o advento da computação e a capacidade de processamento das máquinas, os estudos vêm evoluindo com muita rapidez, porém o custo computacional ainda é muito grande, levando-se em consideração, por exemplo, o teste de primalidade de 243112609 - 1. Por esta dificuldade de fatoração, utilizam-se os números primos na criptografia de dados para transmissão pela web, principalmente o Modelo de Criptografia RSA, que consiste basicamente na obtenção de dois números primos enormes como base para criação da chave pública para cifrar os dados. Assim, fica praticamente impossível alguém obter os divisor do número e achar a chave privada para decifrar os dados. Este trabalho visa quantificar e especificar a complexidade destes cálculos, e conhecer mais um pouco destes números especiais.