Last August, Agrawal, Kayal, and Saxena, all from the Indian Institute of Technology in Kanpur, announced a new algorithm to distinguish between prime numbers and composite numbers. Unlike earlier methods, their method is completely rigorous, deterministic, and runs in ``polynomial time." This last bit means that the number of elementary steps their algorithm spends is bounded by a fixed power of the length (logarithm) of the number being tested. Previous results, some of them quite deep, were close to this ideal in various ways, so, perhaps, it was not such a great surprise that such a result should exist. But the relatively easy algorithm and proof is stunning. In this talk, the new algorithm will be described as well as some new developments that are joint with Hendrik Lenstra.