Na Grécia Antiga, era comum oa filósofos batizarem alguns conjuntos numéricos com determinados nomes que expressavam características não matemáticas, por crerem que tais números possuissem um certo poder e papel determinante na ordem do universo. Dessa forma surgiram os números amigos, perfeitos, primos, defeituosos etc….
Talvez de todos esses conjuntos, o mais famoso seja o dos números primos. Um número é dito primo se ele pertencer ao conjunto dos números naturais maiores que 1 e o seu único divisor maior que 1 é ele próprio, ou seja, ele não pode ser decomposto através de uma multiplicação de números menores que ele, sendo assim “primeiros” na geração dos demais números, ditos compostos.
Essa classificação, quase que ingênua, deu origem a um dos mais belos e longos problemas da história da matemática, a criação de um método eficiente para determinar se um número qualquer é primo, e se não for, quais seus divisores.
A primeira tentativa nesse sentido foi feita por Erastóstenes (285-194 A.C), que criou um método semelhante a uma peneira par determinar quais eram os números primos antes de um outro número dado (vide ilustração abaixo). Nele, eram feitas iterações em que eram removidos dentre os cadidatos a primos os múltiplos dos primos já conhecidos, em um processo que exigia que a sequência fosse percorrida várias e várias vezes, sem muita eficiência.
O problema da determinação dos números primos caminhou junto com a Teoria dos Números, que versa principalmente sobre as propriedades do números inteiros, e acabou deixando mais um problema extremamente simples em termos de compreensão, mas insolúvel ainda, a Conjectura de Goldbach, que diz que qualquer número par maior do que dois pode ser escrito como a soma de dois números primos (não necessariamente distintos).
Aproveitando-se da aparente inexistência de um algoritmo de tempo polinomial para a resolução do problema da determinação dos números primos, diversos algoritmos de criptografia foram criados tendo como base chaves números primos grandes, que exigiririam um grandioso esforço computacional para ser resolvido, o mais conhecido deles é o RSA.
Em 2002 porém, em um artigo intitulado Primes is in P, os pesquisadores do Indian Institute Tecnology of Kanpur, Manindra Agrawal, Neeraj Kayal e Nitin Saxena, expuseram em menos de dez páginas o problema que venceu mentes como Euler e Fermat. O algoritmo de verificação se baseia na seguinte propriedade:
advinda do Pequeno Teorema de Fermat, onde a equivalência se verifica apenas se n for primo. Essa equivalência pode ser verificada em tempo exponencial, o que ainda não era o objetivo do trabalho. Então, para agilizar o teste, abriu-se mão de outra equivalência:
esta sim, pode ser verificada em tempo polinomial.
Ao contrário do que muitos veiculos de imprensa anunciaram, a descoberta de um método eficiente para descobrir se um número é ou não primo, não implica imediatamente no fim da segurança dos sistemas bancários, uma vez que a compleixade assintótica desse algoritmo pode ser ainda muito alta, embora polinomial. O próprio algoritmo AKS tem complexidade da ordem da 12º potência do número de digitos da entrada (na base 10), e mesmo sendo melhorado ainda não avançou muito nesse número, portanto, ao menos por enquanto, nosso dinheiro ainda está bem protegido.
Link do artigo Primes is in P : http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
Password 
Deixe um comentário