En 1975, Rabin también inventó el test de primalidad de Miller-Rabin, un algoritmo aleatorio que determina muy rápidamente (pero con una probabilidad de error minúscula) si un número es primo o no.