Existem basicamente dois tipos de testes para números primos: determinísticos e não-determinísticos. Os determinísticos como os crivos aritméticos, em especial o de Eratóstenes, fazem um trabalho de força bruta sofisticada, mas mesmo assim são bem demorados para primos gigantes. Porém, os testes não-determinísticos, também conhecidos como testes estatísticos são frutos de vários trabalhos que estudam a profunda e enigmática distribuição não-linear dos primos.
Matemáticos como Riemman, Carmichael, Lucas, Lehmer, entre outros, travaram guerras épicas para desenvolver métodos práticos, rápidos e eficientes para identificar primos de forma não-linear. Enfim, tais testes não-determinísticos são extremamente velozes em comparação aos determinísticos e conseguem determinar com uma precisão impressionante com mais de 99% de certeza se uma dado número é primo. Os números que passam nesse teste ou são realmente primos ou são pseudoprimos.
Se um número passar no teste estatístico, só então vai para o teste determinístico.
Com esse teste se verificam números de Mersenne primos gigantes. São rápidos e práticos.
Pergunta: É mais fácil verificar primalidade do que fatorar números gigantes????
[[ ]]'s