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