Mas o que é um número primo?
Um inteiro positivo é primo se tiver apenas 2 divisores. Caso apresente mais de 2 divisores, ele é composto.
Assim são primos os números 2, 3, 5, 7, 11, 13, ... e são compostos os números 4, 6, 8, 9, 10, 12,....
Todo número composto pode ser escrito como um produto de números primos. Por exemplo, o número composto 12 pode ser escrito como 2x2x3 ou 22x3.
Um problema importante na criptografia é saber se um determinado inteiro positivo é ou não primo.
Um método usado para responder a essa questão é o método da "divisão por tentativas".
Esse método consiste em dividir o número dado por todos os números ímpares menores do que a parte inteira da raiz quadrada do número. Se existir um número ímpar como descrito acima, que divide o número dado, esse número não é primo. Caso não exista tal número, então ele é primo.
Embora possa não parecer a primeira vista, tal verificação é extremamente penosa. Experimente, por exemplo, verificar se 1999 é primo. Imagine agora você fazendo essa verificação para um número que tenha, por exemplo, 50 algarismos!!!
Existe um outro algoritmo que permite decidir rapidamente se um número inteiro positivo é primo ou não, só que essa verificação apresenta uma certa probabilidade (muito pequena) de erro.
A grande descoberta de que fala o título deste artigo apareceu no final de 2002. Um professor indiano, Manindra Agrawal, e seus dois alunos, Neeraj Kayal e Nitin Saxena, descobriram um algortimo que está sendo chamado de AKS (iniciais de seus nomes), que permite verificar, sem margem de erro, se um inteiro positivo é ou não primo, em um espaço de tempo relativamente curto.
É interessante observar que durante séculos os matemáticos procuraram um algoritmo como o AKS e ainda mais interessante é a incrível simplicidade desse algoritmo.
Mas uma questão agora se impõe:
Como ficam a partir de agora, os sistemas de criptografia que usam as propriedades dos números primos?
A princípio não há relação entre esses sistemas e o algortimo AKS, pois esses sistemas utilizam a fatoração de números primos e não sua identificação e a princípio o algoritmo AKS não permite dizer quais os fatores primos do número primo considerado.
