Função para descobrir primos grandes (200 dígitos ou +)

[imaia]

Tenho buscado na internet algoritmos de teste de primalidade de números. Deparei-me com o AKS e Monte-Carlo, sendo o AKS determinístico e o M.C. probabilístico, porém o M.C. é muito mais rápido. Contudo li artigos e monografias com gráficos de execução dos referidos algoritmos e eles funcionam bem para primos pequenos, digamos com 6 dígitos, além do que o tempo de resposta cresce de tal maneira que fica inviável testar a primalidade de centenas de dígitos, duraria uma eternidade. Estou supondo que fonte que li está correta.

Então gostaria de saber, se hoje em dia em comércio eletrônico e em protocolos de criptografia usam-se primos grandes, deve existir um meio de obtê-los. Na internet só se mostra listagens de primos pequenos. E os grandes, como descobri-los?

Preciso da informação para realização de software, então qualquer ajuda é muito bem vinda.

[MarceloFantini]

Acredito que se hoje em dia primos grandes são usados em comércio eletrônico e protocolos de criptografia são justamente porque não são fáceis de descobrir. Se existisse tal modo mais fácil de obtê-los todo o esquema de criptografia seria quebrado, qualquer um poderia obter informações que outros querem esconder.

[Renato_RJ]

Boa noite !!!

Mas que assunto interessante !! Primos !!!

Hoje em dia existem maneiras de criar primos enormes, o problema é testá-los, existem diversos testes (como Rabin-Muller utilizado por alguns softwares de matemática, como o Maxima por exemplo) e temos tabelas com números maiores do que 200 dígitos que possuem mais de 97% de chances de serem primos veja em:

http://primes.utm.edu/lists/small/small3.html#300

Agora, o pouco que eu sei sobre criptografia é, atualmente estão estudando um algoritmo um baseado em curvas elípticas (o nome curvas elípticas não tem relação alguma com elipses) pois estas tem uma propriedade bem peculiar, se pegarmos dois pontos na curva (P e R, por exemplo), podemos determinar um terceiro (Q) fazendo apenas a soma desses pontos, mas uma curva elíptica é um anel com a propriedade apenas de soma, logo sabendo-se o ponto P e o ponto Q não temos como descobrir o ponto R (sendo que P + R = Q, lembre-se, é um anel com a propriedade somente de soma, nada mais)... Esse tipo de algoritmo é mais rápido e mais seguro do que o uso de primos enormes (pois devido a incerteza gerada pelos testes, podem ser considerados como pseudo-primos)...
Se quiser saber mais sobre primos existe um excelente livro chamado "Primos" do professor Paulo Ribenboim (é uma excelente leitura, mas a matemática ao longo do livro fica um tanto complexa)...

Abraços...