MathWorld Headline News

Primality Testing Is Easy

By Eric W. Weisstein

August 7, 2002--Prime numbers are integers that have no integer factors other than 1 and themselves. For example, 6 is not a prime since it has factors 2 and 3 in addition to 1 and 6. On the other hand, 7 is a prime since its only factors are 1 and 7. Numbers that are not prime are called composite numbers.

While simple to describe and understand, the properties of prime numbers are unexpectedly elusive, despite that fact that they have been the subject of intense mathematical inquiry since the days of Euclid and Eratosthenes. While Euclid showed that an infinite number of primes exist (this result, now known as Euclid's second theorem, appeared in Proposition IX.20 of Euclid's famous Elements), determining whether a given number is prime or composite, let alone factoring it into its so-called prime factorization if it is composite, has proved a difficult problem. This problem has received immense attention in recent years due to the widespread use of prime numbers in encryption algorithms such as the RSA algorithm. For example, if there were efficient algorithms for factoring large numbers, the vast majority of encrypted electronic communications worldwide would be easily crackable.

Algorithmic complexity theory is a mathematical discipline that classifies problems based on how difficult they are to solve. A problem is assigned to the P-class (where "P" stands for "polynomial-time") if the number of steps needed to solve it is bounded by some power of the problem's size. A problem is assigned to the NP-class (where "NP" stands for "nondeterministic polynomial-time") if it permits a nondeterministic solution and the number of steps to verify the solution is bounded by some power of the problem's size. Primality testing (in other words, determining if a number is prime without actually computing any of its factors), is easier than prime factorization, and has long been believed to be P.

The most efficient prime factorization and primality testing algorithms known today are probabilistic, in the sense that they use sophisticated techniques that will almost always return a result but do not do so with absolute mathematical certainty. For example, a particularly efficient probabilistic algorithm known as the Rabin-Miller strong pseudoprime test is used by Mathematica's PrimeQ command for testing primality.

On August 6, M. Agrawal, N. Kayal, and N. Saxena, all of the Indian Institute of Technology in Kanpur, posted an electronic preprint containing an algorithm that supposedly tests primality in polynomial time (Agrawal et al. 2002). This paper had been distributed earlier to a number of prominent number theorists. Leading experts Hendrik Lenstra (University of California, Berkeley) and Carl Pomerance (Bell Labs) have already commented on the paper, stating that its results are correct, clever, and elegant (Clark 2002, Pomerance 2002). While the asymptotic time complexity of the algorithm has been proved to be O(ln¹²n) for an integer n (meaning that the running time is proportional to the 12th power of the natural logarithm of the number being tested), heuristics suggest that in practice the algorithm has time complexity O(ln⁶n), which can be further reduced to O(ln³n) if one additional number theoretical conjecture can be proved.

Faster primality testing does not pose any immediate risk to the security of electronic communication. However, it does open up the possibility for greatly speeding up mathematical computation in many areas of number theory. It is too early to say whether the new algorithm can be implemented in such a way as to be competitive with fast probabilistic methods. But as a method of authoritatively distinguishing probable primes (primes that appear to be prime based on some test or sets of tests but for which this cannot be rigorously established) from actual primes, it may already be one of the fastest algorithms in town!