Um
teste de primalidade é um
algoritmo para determinar se um dado número inteiro é
primo. Este tipo de teste é usado em áreas da
matemática como a
criptografia. Diferentemente da fatoração de inteiros, os testes de primalidade geralmente não fornecem os fatores primos, indicando apenas se o número fornecido é ou não primo. O problema da fatoração é computacionalmente difícil, enquanto que os testes de primalidade são comparativamente mais fáceis (o tempo de execução é polinomial no tamanho dos dados de entrada). Alguns testes de primalidade
provam que um número é primo, enquanto que outros, como o teste de Miller-Rabin provam que um número é composto.