polynomial-time 3

Tetris is NP-Hard. Let me explain, in English, what that means. The toughness of problems is how much time it takes to solve them. Adding two 3-digit number takes less time than adding two 30-digit numbers, and hence is easier. Similarly, figuring out if a 3-digit number is prime or not is easier than a 30-digit number. Some problems grow tough very quickly. Adding two 30-digit numbers is 10-times slower than adding two 3-digit numbers. But checking if a 30-digit number is prime is several trillions of times slower than checking a 3-digit number. That is because, to check if a number is prime, you need to repeatedly divide it by numbers smaller than it. For a 3-digit number, you need to divide by around 1,000 numbers. For a 30 digit number, it’s several trillions. ...

Progress on the polynomial-time computability of prime numbers.

Prof. Manindra Agarwal and his students at IIT-K have figured out a polynomial time test for primality. It was an unsolved problem. The RSA algorithm assumes that this is impossible. (NYTimes) Of course, others have claimed the same. To my knowledge, none is conclusively proven. What if they’re true? Well, in a few years, our cryptography algorithms will be useless. So it’s back to the drawing board, with security-related dot-coms from Univs popping up.