Os testes modernos de primalidade para números gerais n podem ser divididos em duas classes principais, algoritmos probabilístico (ou "Monte Carlo") e determinístico. Os algoritmos determinísticos fornecem uma maneira de saber com certeza se um determinado número é primo ou não. Por exemplo, a divisão de teste é um algoritmo determinístico porque, se executado corretamente, sempre identificará um número primo como primo e um número composto como composto. Os algoritmos probabilísticos são normalmente mais rápidos, mas não provam completamente que um número é primo. Esses testes dependem do teste de um determinado número de maneira parcialmente aleatória. Por exemplo, um determinado teste pode passar o tempo todo se aplicado a um número primo, mas somente com probabilidade p se aplicado a um número composto. Se repetirmos o teste n vezes e passarmos sempre, a probabilidade de nosso número ser composto é 1 / (1-p) n, que diminui exponencialmente com o número de testes, para que possamos ter a certeza que quisermos (embora nunca perfeitamente certo) de que o número é primo. Por outro lado, se o teste falhar, sabemos que o número é composto.
Ao usar um algoritmo probabilístico, como é que a probabilidade de que o número seja composto seja expressa matematicamente?
1 / (1-p) n