I moderni test di primarietà per i numeri generali n possono essere suddivisi in due classi principali, probabilistiche (o "Monte Carlo") e algoritmi deterministici. Gli algoritmi deterministici forniscono un modo per sapere con certezza se un dato numero è o meno di prim' ordine. Per esempio, la divisione di prova è un algoritmo deterministico perchè, se eseguita correttamente, identificherà sempre un numero primo come primo e un numero composito come composito. Gli algoritmi probabilistici sono normalmente più veloci, ma non dimostrano completamente che un numero è al primo posto. Questi test si basano sulla prova di un dato numero in modo parzialmente casuale. Ad esempio, una data prova potrebbe passare per tutto il tempo se applicata ad un primo numero, ma passare solo con probabilità p se applicata ad un numero composito. Se ripetiamo il test n volte e passiamo ogni volta, allora la probabilità che il nostro numero è composito è 1/ (1-p)n, che diminuisce esponenzialmente con il numero di test, quindi possiamo essere sicuri come ci piace (anche se mai perfettamente sicuro) che il numero è primo. D' altra parte, se il test dovesse mai fallire, allora sappiamo che il numero è composito.
Quando si utilizza un algoritmo probabilistico, come è la probabilità che il numero sia composito espresso matematicamente?
1/ (1-p)n 1/ (1-p)n 1/ (1-p)n 1/ (1-p)n 1/ (1-p)n