Finding out whether a given number n is a prime or not is a problem that
was formulated in ancient times, and has caught the interest of mathematicians again and again for centuries. Only in the 20th century, with the advent
of cryptographic systems that actually used large prime numbers, did it turn
out to be of practical importance to be able to distinguish prime numbers
and composite numbers of significant size. Readily, algorithms were provided
that solved the problem very efficiently and satisfactorily for all practical
purposes, and provably enjoyed a time bound polynomial in the number of
digits needed to write down the input number n. The only drawback of these
algorithms is that they use “randomization” — that means the computer
that carries out the algorithm performs random experiments, and there is a
slight chance that the outcome might be wrong, or that the running time
might not be polynomial. To find an algorithm that gets by without randomness, solves the problem error-free, and has polynomial running time had
been an eminent open problem in complexity theory for decades when the
paper by Agrawal, Kayal, and Saxena hit the web. The news of this amazing
result spread very fast around the world among scientists interested in the
theory of computation, cryptology, and number theory; within days it even
reached The New York Times, which is quite unusual for a topic in theoretical
computer science.