The World According to Eratosthenes

Primes is in P
A 2200 year old math problem solved!

This past month a headline in the New York Times excited a lot of mathematicians, while the non-mathematical world wondered what the big deal was. Three computer scientists in India found a deterministic algorithm for deciding if a number is prime in polynomial time.

For you non-math people, it is probably better to say that the three computer scientists found a "quick and easy way to determine if a number is prime that is right all the time". To tell you the truth, it is not really that quick, or that easy, but it is far quicker and easier and more accurate than any method we have had up to this point.

With a new school year in session, I thought I would attempt to explain this new method in easy enough terms that a High School or College Algebra student might be able to follow it. Of course dropping the math that low will require dropping explanations of the proofs, and I may need to quickly explain some of the more advanced concepts. I have decided to make liberal use of Eric Weisstein's World of Mathematics web site to explain some of the concepts like prime numbers, although if you do not know what a prime number is, I doubt you have little chance of understanding this essay/lesson.

While I doubt most readers will understand everything in this lesson, chances are you will at least learn a thing or two about number theory (I know I did in writing it) -- and what is wrong with a little new knowledge?

A Brief History of Prime

While the prime concept has probably been around since the Babylonian's time, the first person to study the subject of primes enough to come up with a method for finding them was Eratosthenes, a 3rd Century B.C. Greek cartographer who is most famous for drawing one of the earliest known maps of the world (see the picture above) and finding the circumference of the Earth about 1700 years before anyone sailed around it -- and he was only off by about 80 km.

He invented a way to determine primes called "Eratosthenes' Sieve", a method of sifting out composite numbers, leaving only the primes. This he did by writing all the odd numbers (starting with 3, 1 was not considered a "number" by the Greeks) and then canceling the successive multiples one after the other, thus: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, ... Meanwhile, Euclid proved that an infinite number of primes exists.

While the Sieve method works fine for small prime numbers, it's difficulty increases exponentially with bigger and bigger numbers. So much so that it would require a computer the size of the entire universe to determine if 2257 - 1 is prime or not. (there are only 2300 atoms in the entire universe in which to enumerate for the sieve to work.)

The importance of finding prime numbers easily is obvious from all those fraction problems we had to do in school. Of even bigger importance is the "Fundamental Theorem of Arithmetic" which states that every integer has a one unique prime factorization. Hence the knowledge of primes is of high importance in every field of number theory. 

Fast Forward to 17th Century France, where mathematicians started looking at the set of prime numbers in hoping of identifying patterns that could be exploited. One of the most famous mathematicians of the day was Father Marin Mersenne who stated that 2p - 1 is prime when p = 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257. He was wrong about 67 and 257, and he missed 61, 89, and 107. Still we now call any prime of the form 2p - 1 a Mersenne prime in his honor.

Another prime pioneer was a friend of Mersenne named Pierre de Fermat, creator of the famous "Fermat's last theorem" that was only recently proven by Wylie. Fermat, who actually made his living as a lawyer, created numerous conjectures about prime numbers, some of which proved false, but which ended up being extremely important to the latest solution. The most important was this "little prime theorem":

If p is prime then for every x Î [1, p-1], x(p-1) º 1 (mod p)

If you are not up on modulo congruence, this may not make much sense, but give it a try if you have a mod key on your calculator (the built in calculator in Windows has one). Pick a prime number, say 11 and that is p. then pick any number x from 1 to 10 (10 = p - 1), say x = 6. Now using your calculator, press 6 "x^y" 10 "mod" 11 "=" and the answer is 1. Try making p a non-prime and see what happens.

The problem with Fermat's little prime theorem is that while it works for all prime p's it also works for some composite (non-prime) p's as well. Try p = 15 and x = 4, sure enough the answer is 1 even though 15 is not prime. If you change x to anything else < 14 it seems to work fine. Worse still are Carmichael Numbers which are composite numbers but behave like primes no matter what x you use. 

There are other known qualities of primes that also turn out to be true of some composites, but Fermat's is the easiest. There are also qualities of primes which are absolute and fail for all composite numbers such as Wilson's Theorem first proposed in 1770:

If and only if p is prime, then (p - 1)! + 1 º 0 (mod p)

The problem with this test (which works on any prime and fails on every composite number) is that (p - 1)! is extremely long and difficult to calculate. It is great if p is small, but again if you are testing if 2257 - 1 is prime then you may find that (2257 - 2)! is a number so big that the digits exceed the number of atoms in the known universe, and thus we are back to square one(1).

Gauss, one of the greatest mathematicians in history, once said the following about finding an easy way to find prime numbers:

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent ... [that] the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Primes in the Age of Computers

In 1876, French mathematician Edouard Lucas developed a method for testing the primality of Mersenne primes. He used it to prove that 2127 - 1 is prime. To this date it stands as the largest prime found by hand calculations. Around 1951, an American mathematician named Dick Lehmer refined Lucas' method and programmed it into one of the first computers called SWAC. On January 30, 1952, he used the computer to prove that 2521 - 1 is prime, then had time left over to prove that 2607 - 1 is also prime. The SWAC team went on to find two more Mersenne primes that year, but larger primes seemed to be beyond the reach of that machine.

Since then it has almost become traditional to christen the latest supercomputer by giving it a record high prime to prove. Not only does it give the hardware a good work out, it gives the computer manufacturer some bragging rights. 

All that changed in 1996, as the first of 5 Mersenne primes were discovered using desktop computers. Using free Lucas-Lehmer software, and coordinated over the internet, the Great Internet Mersenne Prime Search (GIMPS) has tested systematically every possible Mersenne number for primality. The latest 213466917-1 was proven prime in 2001, and still holds the record today. 

As you might suspect, these records are not shattered using Eratosthenes Sieve, they used more complicated, but much faster methods(2). For example, to prove a number n is prime, you do not really need to test if any of the numbers below it are factors. All you really need to test are if any primes less than the square root of n are factors. This lessens the calculating load considerably, as long as you know all the primes less than the square root of n. Over the years, mathematicians and programmers have discovered other shortcuts, and have written software to test for primes that is faster and more efficient with each generation. Still an important goal has eluded them...

To P or NP

For the past century, the "holy grail" of prime routines was to find a test for primes of complexity P. Here is where a little explaining is required. In order for a routine to be of complexity P, it has to have two qualities:

  1. The routine must be deterministic, which is to say it ALWAYS returns the exact right answer. It is much easier to find routines that are non-deterministic, which are right 99.99999% of the time -- good enough for most uses, but we can never be sure they are exactly right. Such routines are called NP class*.

  2. The complexity must be a polynomial, that is to say: as n increases, the time it takes to come up with an answer is less than nc where c is a constant (no variables allowed in the exponent).

The need for the second one is evident when you consider growth. Compare how quickly 2n rises as n gets bigger (2, 4, 8, 16, 32, 64...) with the growth of n2 (1, 4, 9, 16, 25, 36, ...), while in the early going they are about the same, by the time n = 6 the former is already nearly twice as big, and it only gets worse from there. (49 vs. 128, 64 vs. 256, etc.)

Up till now, every test for primality has either been non-deterministic (failing test 1) or of exponential complexity (failing test 2). Before I try to explain the first ever P test for primality, a little review of the past failures is in order.

Before I go on, a little notation review/introduction is in order. Complexity is represented as O(f(n)), where f(n) is the growth in time it takes to get an answer as n increases. Complexity always takes into consideration the worst case scenario(3). 

Deterministic, but Not Polynomial Tests

In 1980, Adleman and Rumely developed a test that would decide if a randomly chosen number up to 100 digits was prime in 4 to 12 hours with a large computer, such as a CRAY supercomputer. Around 1983, Cohen and Lenstra improved the program around 1000 times, so now a 100 digit number could be tested for primality in about 40 seconds on a supercomputer.

The routine they used had a complexity of (log n)O(log log log n) which is considerably better than exponential time, but since that pesky n is still in the exponent, it is still not "polynomial" time (hence not in P)

Since then there have been programs based on prime conjectures (unproven theories) which would run in polynomial time, but since the conjectures were unproven, they did not count.

Polynomial, but Not Deterministic Tests

While the goal of a P test for primes remained elusive, in 1980 Michael O. Rabin invented a "monte carlo" test in P that would quickly determine if a very large number was likely to be prime. To decide if number p was prime, Rabin would pick a random number r between 2 and p - 1and apply two tests:

  1. rp-1 > 1 (mod p),

  2. and for some integer k, 1 < gcd(r(p-1)/2k - 1, p) < p

Note the first test is based on Fermat's "little prime theorem" mentioned above, and the second test is obvious since if p has a factor > 1 it is not prime by definition. 

By theorem, better than half of the r values between 2 and p - 1 will pass both tests if p is not prime, thus according to Rabin they are "witnesses to the compositeness of p". So, if both tests pass, then p is not prime. If a test fails then there is better than 50% chance that p is prime. So we pick a second r and try the tests again. If another test fails, then the odds of p being prime is now 75%. For every r that we pick and the tests fails, we double the likelihood of p being prime. So picking 10 r's and all of them failing leads to a 99.9% likelihood of p being prime, which is pretty good.

Other "Monte Carlo" prime tests have been proposed, such as this one by Solvay and Strassen, but as you can tell, as accurate as these tests are, they still do not guarantee the right answer, thus "non deterministic" and not in P.

They are, however, accurate enough to be used extensively in cryptography. The Miller-Rabin test (as it is commonly called) can take advantage of binary math to run pretty fast on any computer. The Miller Rabin test occasionally runs on your computer somewhere as part of the encryption-decryption process needed for secure networking. Until a faster deterministic test can be found (and the new Agrawal-Kayal-Saxena Test is no where near as fast), this prime test will be the test of choice.

Here is the big question about these tests: Is it possible to find an r or a set of r's that when applied to one of these tests, guarantees a right answer (thus making the test deterministic)?

The Agrawal -Kayal -Saxena Test

The answer is "yes", according to three computer scientists Indian Institute of Technology in Kanpur (IITK) named Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. They devised a new "Monte Carlo" test based on a corollary of Fermat's prime theorem, then found a small set of r's that would determine if a number is prime guaranteed.

The pseudo algorithm goes as follows:

  1. Input: Integer n > 1 

  2. if (n has the form ab with b > 1) then output COMPOSITE;

  3. r := 2;

  4. while (r < n) { 

  5.    if (gcd(n,r) is not 1) then output COMPOSITE;

  6.    if (r is prime greater than 2) then {

  7.       let q be the largest factor of r-1;

  8.       if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then 

  9.           break; 

  10.       } 

  11.    r := r + 1;

  12. } 

  13. for a := 1 to 2sqrt(r)log n { 

  14.    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE; 

  15. } 

  16. output PRIME;

While understanding how it works is a bit difficult, the routine is fairly easy to follow, except line 14. So, let me explain line 14 first. It is based on this corollary to Fermat's Little Prime Theorem:

Theorem A:  Suppose that a and p are relatively prime integers with p > 1.  p is prime if and only if

(x - a)p º (xp - a) (mod p)
Proof.  If p is prime, then p divides the binomial coefficients pCr for r = 1, 2, ... p-1.  This shows that (x-1)p = (xp-ap) (mod p), and the equation above follows via Fermat's Little Theorem.  On the other hand, if p > 1 is composite, then it has a prime divisor q.  Let qk be the greatest power of q that divides p. Then qk does not divide pCq and is relatively prime to ap-q, so the coefficient of the term xq on the left of the equation in the theorem is not zero, but it is on the right.

The key to understanding this theorem is to recognize that x is meaningless here. We only really care about the coefficients of the polynomial
 (x - a)p. As you may recall from Algebra, raising a binomial to a power p results in a polynomial of degree p with p + 1 terms. 

All but the first and the last term are going to be positive or negative integers with absolute value > 1. If p is prime and a is relatively prime to p, then all of these coefficients will be divisible by p, thus modulo p of each term = 0 except for the first term xp and the last term -ap (which modulo p = -a, since a and p are relatively prime).

The problem is that it still takes exponential time to determine if p is prime using this test, because you have to calculate p-1 coefficients and divide all by p to see if there is a remainder.

In 1999, Dr. Agrawal proposed a monte carlo test, which you can read about here, based on this theorem. To shorten the test and bring it in P, the polynomial (x - a)p would be shortened by applying modulo xr - 1, which is just a fancy but short way of saying "lets just look at the last r terms of (x - a)p" (4). 

If r is sufficiently large enough, the only composite numbers that will sneak in are powers of odd primes which can be tested for separately using a much easier test also in P. If you look at the algorithm, line 2 does exactly that test.

This make sense, because if you look at Pascal's Triangle, all of the binomial coefficients in which n = prime or a power of an odd prime are all divisible by n (except for the 1's at the beginning and the ending of each line). In the first 10 lines of Pascal's triangle, all of the numbers in lines 2, 3, 5, 7, and 9 are divisible by the line number, while lines 4, 6, 8 and 10 have numbers that are not divisible, all being composites. Line 9 is the only odd line since it is a power of an odd prime (3*3) (5).

So, to make a deterministic test in P, all we need to do is select an r big enough to rule out all composite p's that are not powers of primes, but small enough to keep the complexity (growth) of the routine from being exponential.

In 2000, Kayal and Saxena used an unproven conjecture to to determine that r does not need to exceed 4(log2 p), this paper can be found here. Thus, the time complexity of their routine is an amazing O(log3 n) and easily in P. Still, an unproven conjecture is an unproven conjecture.

Instead of trying to prove the conjecture, what Drs. Agrawal, Kayal, and Saxena did was use a proven prime theorem relating to Sophie Germain Primes. They proved that if you find a Sophie Germain pair of primes q and 2q +1 such that q > 4(sqrt(2q +1)) log p, then r does not need to exceed 2(sqrt(2q + 1) log p. Their paper can be found here. A peer review that details the theorem can be found here.

The biggest negative of this fix, is that the resulting test for primes becomes a recursive test as you can see from line 6 of the algorithm above. In order to test for prime p we have to test for prime r, etc. This causes our nice little O(log3 n) test to grow to an unwieldy but still polynomial O(log12 n).

So the explanation of the Algorithm is as follows:

  • Line 1 inputs n
  • Line 2 determines if n is a power of an odd prime (the only case that the rest of the routine will fail on) and returns COMPOSITE if it is.
  • Line 3 and 4 initialize the first required loop of r that ends on line 11 and 12.
  • Line 5 determines if n and r are relatively prime (required by the Theorem A).
  • Line 6 determines if r is prime, thus requiring a recursive call to the routine with r as the input.
  • Lines 6 to 10 find the required Sophie Germain pair of primes and sets r to the highest of the two.
  • Lines 13 to 15 are the second loop of a.
  • Line 14 plugs in values a and r to Agrawal's prime test.

Now as far as I know, no one has written an actual computer program to apply this test (though there are no doubt some graduate students at IITK working on doing just that.), and because of the large -- but still polynomial -- complexity, it may prove too much of a memory burden to test on really big numbers. 

The real importance of this discovery is that finding primes is indeed in P, making much easier routines theoretically possible. This has been a goal of mathematicians now for 2200 years.

Footnotes:

1. If you look at Fermat's formula, you are probably thinking "isn't calculating xp-1 also as difficult as calculating (p-1)! ?" This is true if you do it the hard way, but there exists shortcuts to the former, like breaking p-1 into binary and mod p the individual powers of two, that cannot be done with factorials.

2. The GIMPS project uses the exact software algorithms used by SWAC in the early 50's, which says a lot about computer progress. Today's desktops are far superior to even the best "supercomputers" that existed in the early '70s, and prime testing proves it.

3. For example, say you are putting a set of files in alphabetical order. You grab the first file, then you get the second file and compare it with the first, and put it either in front or behind the first. Each file you grab requires you start from the front of sorted files , and compare it with each file until you find a file greater than the one you are sorting then you put that file in front. The worse case scenario is that the files are in reverse alphabetical order. In that case the first file requires one comparison, the second two, the third three, etc. So, if you remember the formula for adding 1+2+3+4...+n the most comparisons we have to make is (n2 - n)/2. Generally, we only care about the term with the highest degree when representing complexity, so complexity in this case is O(n2/2) which makes sorting files in P since our routine correctly alphabetizes and 1/2 n2 is a polynomial.

4. Recall from Algebra that if you divide a polynomial of degree p by a polynomial of degree r, the result will be a polynomial of degree p - r, with the remainder being a polynomial of degree r - 1. The remainder in the case of dividing by xr - 1 should be the last r terms of the polynomial. Unless I am wrong about this, line 14 could be replaced with:
For i := 2 to r-1
   if ((-1)i * nCi * a(n - i)) mod n <> 0 then output COMPOSITE
next i
 UPDATE: I got a couple of notes indicating my analysis is wrong, which I suspected as a possibility (hence the 'unless I am wrong' disclaimer above). This is the easier to understand of the two notes:

Hi, Paul: A friend referred me to your page on the "primes in P" algorithm by Agarwal et al.
 Your footnote 4 asserts that division by polynomial x^r - 1 gives as remainder the last r terms of the dividend.  This is incorrect.
 If you were dividing by x^r, the remainder would be the last r terms of the dividend.  But not so with division by x^r - 1.
 An example:
 Divide (x + 1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 by (x^3 - 1).
 Remainder is 11x^2 + 10x + 11.
 Conceivably yours was an intentional "mistake" but in any case I thought it opened an interesting light on the algorithm.  One is led by this mistake to ask how many binomial coefficients C(n,k) need to be checked to determine the primality of n.  This would actually be a very efficient computation to do, while the computation mod x^r - 1 would likely involve a Fast Fourier Transform to do the polynomial multiplication.
 Regards,
Chip

A couple of notes: First, the Fast Fourier Transformation (also known as FFT, a computer algorithm created by Donald Knuth) is exactly what is recommended for this operation. Second, the remainder is of a degree r - 1 and only contains r terms, so at least I was right about that. But, here is the important part: Note what happens when that remainder modulo 5 is calculated, the result is x^2 + 1, which is exactly what it should be if 5 is prime per Theorem A.

5. In practice, if we were to use Theorem A to test if p was prime, and p turned out to be a composite number other than a power of an odd prime, then the coefficient mod p = 0 test would fail early and often. The question is how early and often? That is what is needed to find a suitable r.

* A Note from a reader krzysztof : NP stands for nondeterministic polynomial and is the class of languages that can be detected in poly time by a nondeterministic turing machine, there's nothing about randomness in it!! The class you describe could be either RP, Co-RP or BPP, depending on what  type of error (never err if n is prime -> RP, never err if n if composite -> Co-RP, err in both cases -> BPP) primes was known to be in ZPP which is RP and Co-RP or in other words expected (deterministic) polynomial time. 
Sorry if that was unclear, I did not mean to imply that randomness has anything to do with NP. The fact that these routines cannot guarantee a correct answer (and randomness has nothing to do with that fact) makes them 'non-deterministic' by definition, but not necessarily NP. In an upcoming essay, I will look at NP in detail as part of a discussion of the "traveling salesman problem"

Thanks also to The Prime Pages web site, The Turing Omnibus by A. K. Dewdney and The Penguin Dictionary of Curious and Interesting Numbers by David Wells for some much needed help on this essay.

There is also a PRIMES in P FAQ available that covers some of the above info in more detail.

Back to the Glossary
Back to Archives