For decades after Miller and Rabin’s work, it wasn’t known whether there would ever be an efficient algorithm that allows testing primality in deterministic fashion, with absolute certainty. In 2002, one such method did get discovered by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena at the Indian Institute of Technology—but randomized algorithms like Miller-Rabin are much faster and thus are still the ones used in practice today.
