è un algoritmo per decidere se un numero q è primo. È un algoritmo probabilistico: la risposta può essere o che q è sicuramente composto, oppure una stima della probabilità che q sia primo.

Se il risultato è "composto" il numero q è sicuramente composto. Se no si può ripetere il procedimento a partire dal passo (2) per un certo numero di volte. Se la risposta è sempre "probabilmente primo" allora q è primo con un'alta probabilità, tanto maggiore quanto maggiore è il numero di iterazioni. Ad esempio, se dopo 10 iterazioni la risposta è sempre "probabilmente primo", la probabilità di errore è di circa 1 su 1 milione, dopo 20 iterazioni di circa 1 su 1000 miliardi.

Perchè funziona?