The complexity of prime number tests

Abstract

Prime numbers have been a significant focus of mathematics throughout the years. Although the study of prime numbers may seem at first quite simple, perhaps because every schoolchild knows what a prime number is, the search for all of the secrets of prime numbers is far from over. Even one of the most famous, thus far unsolved, problems in mathematical history is directly linked to prime numbers, namely the Riemann Hypothesis. Until 2002, it was simply assumed that prime numbers can be differentiated from composites in polynomial time with a great deal of certainty; however, there was no definite proof to say this problem can be solved in polynomial time. If the General Riemann Hypothesis is true, though, some algorithms would classify as deterministic polynomial. If a counterexample for such an algorithm can be found, the test would not longer be classified as deterministic but rather probabilistic. In 2002, though, three Indian mathematicians developed a deterministic algorithm that runs in polynomial time; it is totally independent not only from the Riemann Hypothesis but also all other conjectures - the first of its kind. This result is, of course, groundbreaking for not only the specific field of number theory but also all of mathematics. The development of such an algorithm proves that the prime number problem can be deterministically solved in polynomial time. Additionally, following this initial discovery, further optimizations have been made by other researchers.