O teste de primalidade e a fatoração são dois problemas distintos. Se nos restringirmos ao teste de primalidade, não é preciso conhecer os fatores pois a única questão que precisa ser respondida é "o número em questão é primo ou composto?".

Existem alguns clássicos nesta área da Matemática. O teorema de Wilson, por exemplo, diz que o inteiro p é primo se, e apenas se (p-1)! for congruente a -1 (mod p). Como não se conhece um método para calcular rapidamente (N-1)! (mod N) em, digamos log N passos, a caracterização de primos de Wilson não tem valor prático para testar a primalidade de N.

Existem vários testes de primalidade diferentes. Estes testes podem ser classificados em pelo menos três categorias:

• Testes para números especiais X Testes para números genéricos
• Testes com justificação completa X Testes com justificação baseada em conjecturas
• Testes determinísticos X Testes probabilísticos ou Monte Carlo

Teste de Miller

Em 1976, G. L. Miller propôs um teste de primalidade que era justificado usando uma forma generalizada da hipótese de Riemann.

Teste APR

O teste de primalidade idealizado por L. M. Adleman, C. Pomerance e R. S. Rumely em 1983, também conhecido como teste APR, foi uma grande inovação porque:

• Pode ser aplicado a qualquer número natural N e não requer o conhecimento dos fatores de N - 1 ou N + 1.
• O tempo de processamento t(N) é praticamente polinomial.
• O teste é justificado rigorosamente e, pela primeira vez neste domínio, é necessário apelar para resultados profundos na teoria dos números algébricos; envolve cálculos com raízes unitárias e a lei geral da reciprocidade para a potência do símbolo residual.

O tempo de processamento do APR é um recorde mundial para um teste de primalidade determinístico.

Logo depois, em 1984, H. Cohen e A. K. Lenstra modificaram o teste APR tornando-o mais flexível. Usaram somas de Jacobi na prova (ao invés da lei da reciprocidade) e programaram o novo teste para ser usado em aplicações práticas. Este é o primeiro teste de primalidade de que se tem notícia capaz de lidar com números com até 100 dígitos decimais precisando de apenas alguns segundos.

Testes Monte Carlo

Ribenboim menciona três testes Monte Carlo: o de R. Baillie e Wagstaff, Jr. (1980), de R. Solovay e V. Strassen (1977) e o de M. O. Rabin (1976, 1980).

ECPP

Elliptic Curves Primality Proving, ECPP, é um algoritmo determinístico que fornece um certificado de primalidade para números que podem ser tão grandes quanto 10¹⁰⁰⁰.