Numeros primos

HISTÓRIA DOS NÚMEROS PRIMOS

Há evidências, em registros dos antigos egípcios, de que eles tenham algum conhecimento sobre número primos. O Papiro egípcio de Ahmes ou de Rhind, de cerca de 1650 A.C, era um papiro onde um escriba de nome Ahmes ensinava as soluções de 85 problemas de aritmética e geometria. Mais tarde, no século XIX, este papiro foi encontrado pelo egiptólogo inglês Rhind. Curiosamente, neste papiro, os números primos foram escritos de forma diferente dos números compostos. O escriba Ahmes é o mais antigo matemático registrado na História. Contudo, o mais antigo registro de estudo explícito dos números primos vem dos antigos gregos. Os Elementos de Euclides contém importantes teoremas sobre os números primos, incluindo a infinitude dos primos e o teorema fundamental da aritmética. Euclides também mostrou como criar um número perfeito a partir de um número primo de Mersenne.
A primeira forma de se computar números primos é conhecida como Crivo de Eratosthenes, embora, números primos maiores encontrados atualmente não sejam gerados desta maneira.
Em 1640, Pierre de Fermat declarou o Pequeno Teorema de Fermat, somente provado mais tarde por Leibnitz e Euler. Fermat conjecturou que todos os números da forma a são primos. No entanto, Euler descobriu alguns anos depois que o número 232 + 1 é composto. O francês Marin Mersenne percebeu que alguns primos são da forma 2p – 1, onde p é primo. Em sua homenagem, estes números são chamados de Primos de Mersenne.
No início do século XIX, Legendre e Gauss conjecturaram que quando x tende a infinito, o número de primos até x é, assintoticamente, x/ln(x).
Muitos matemáticos têm trabalhado sobre testes de primalidade para números longos, no entanto, com restrições quanto à forma específica do número. Os algoritmos mais recentes como APRT-CL, ECPP E AKS funcionam com qualquer número, porém, permanecem muito lentos.
Por muito tempo, se pensou que os números primos não tivessem nenhuma possível aplicação fora da