Blogtrek

PRIMES is in P

That is grammatically correct. The problem called PRIMES is that of asking of a number whether it is a prime number or not; that is, whether it is divisible only by itself and 1. If I say 2773 = 47 x 59, you can check it out by multiplying those two numbers. To see whether 2773 is prime or not, we need to check all the numbers below 2773 to see if they divide 2773. There are tricks, such as only checking up to the square root of 2773, and only checking prime or odd numbers, but it still is a tedious task for large numbers. Fortunately, there is Fermat's little theorem which states that if you raise, say, 3 to the 2542 power and keep only the remainder upon division by 2543, then if 2543 is prime, you will get 1. But many composite numbers such as 561 will give 1 as well, so this is not quite a good test for primality. But if you bang around for numbers and raise them to the one-less power and get 1 every time, that is evidence, but not conclusive, that the number is prime. It was an open question as to whether it was easy to prove it is prime.

I heard in the news recently that the problem was proven to be easy; that is, "in P". This means the time it takes to solve it is proportional to some power or polynomial on the number of digits in the number. Checking each divisor out is exponentially complicated - the time it takes explodes exponentially with the number of digits in the number. The Indian mathematicians Manindra Aginwal, Nitin Saxena, and Neeraj Kayal found a much easier way of doing it, and have printed it in a paper that is available by going to http://www.cse.iitk.ac.in/news/primality.html. You apply their algorithm to a number p, and in a fairly short time the computer says that it is either prime or composite. If it says it is prime, that settles it. If it says it is composite, then you have absolutely no idea of what the factors are. That is a much harder problem - so hard that secret codes and encryption are based on it.

So one by one these problems are being settled. The big one, that of P = NP, is still a long way from being solved. Will I see it in my lifetime?