Algoritmo 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.

[josesousa]

Não existe um método simples para números muito grandes. Por isso se codificam as mensagens (RSA) com o produto de dois primos muito grandes. A factorização é uma operação que leva imenso tempo, exponencialmente mais para números grandes.

Por isso a usam no comercio electronico. Normalmente cada um dos lados sabe um dos primos e facilmente descodifica. Qualquer intruso tem um número enorme que tem de factorizar em dois números primos, e encontrar números primos grandes é difícil.

Não posso ajudar muito com algoritmos, mas Monte Carlo não é a solução para muita rapidez

[imaia]

Se alguém puder colocar aqui as regras (algoritmo) Rabin-Miller para testar primalidade eu agradeceria bastante. Não adianta copiar de wikipédia pois de fontes evidentes já consultei. Gostaria de uma descrição cujo jargão matemático fosse mastigado a fim de que eu possa utilizar os operadores matemáticos básicos para implementar software de cálculo de primo. A explicação deve dispensar considerações teóricas e notações de conjuntos numéricos e coisas que não contribuam para serem TRADUZIDAS em contas. Alguém se habilita? ;-)

[imaia]

Ué? O algoritmo na wikipedia tem menos de 1 palmo de extensão... Será que não tem 1 matemático por aqui que dê conta de explicar Miller Rabin???

[imaia]

Acabo de obter a resposta, passar bem a todos. []s