Prime numbers are prized commodities when it comes to cryptographic schemes to keep digital messages, such as credit card numbers, secret on the Internet. The basis of most encryption methods is two very large primes that are multiplied together. The key to breaking the encrypted message is to retrieve the two factors of the resulting product—an undertaking that is not feasible because it would be enormously time consuming. Since even the fastest number-crunching computers would require days, weeks, or years to find the prime factors of a number that is a few hundred digits long, users of Internet business sites can rest assured that their credit card numbers are not accessible to anyone, provided of course that the right software is used. Only those who actually possess the key, that is, who know the prime factors, can decipher the encrypted message.

To use this encryption method, one needs to be sure that the numbers used for encoding are indeed primes. If they were not, they would be divisible into further components, and the factorization of the product would not yield a unique result. (Multiplying the two nonprimes 6 and 14 gives 84. This product could then be split into different pairs of factors—for example, 3 and 28 or 7 and 12.) In these cases some of the keys would be the correct ones, and some would be the wrong ones. So to avoid confusion, potential keys need to be certified as being prime before being used.

But proving that a number is prime is no easy feat. Existing algorithms that can certify that numbers are indeed prime are either very time consuming or, if they are fast, are able to certify the primality of an integer only with a certain probability. Practitioners yearn for an algorithm that is able to tell with certainty and in a speedy way whether a number is prime or not.

This is exactly what a team of three Indian computer scientists managed to devise. Manindra Agarwal and two of his students, Neerja Kayal and Nitin Saxena, at the Indian Institute of Technology in Kanpur utilized and extended Fermat’s theorem—the so-called little theorem, not the more famous “last” theorem—to check for the primality of numbers. After devising their scheme, analysis of the computer program showed a most surprising result. The time required to check for primality did not grow exponentially with the number’s size but merely had a polynomial run time.

It did not take more than a few days after the mathematicians announced their research results on the Internet until news agencies and media around the world picked up on the news. They celebrated the discovery as a breakthrough. The announcements were slightly exaggerated, even though on a theoretical level the three computer scientists did achieve a breakthrough. In mathematics the term “merely” (as in “merely” polynomial) is very relative. The running time of the algorithm that the Indian professor and his students proposed is indeed polynomial in N, with N representing the number of digits in the target integer. But it is proportional to N¹², which means that checking a 30-digit prime number—which in cryptographic terms is an extremely small key—requires on the order of 30¹² computational steps.

Considering that the 1,000 largest primes known today all are over 40,000 digits long—the current world record lists a prime with 4 million digits—one quickly realizes that putting the discovered algorithm into practice is another matter altogether.

Nevertheless, this unexpected result created no small sensation among colleagues in the field. The three mathematicians had hit on a beautiful and fundamentally new idea. For practical purposes the algorithm is, admittedly, still too time consuming. But now that the ice has been broken, experts are confident that more efficient ways of calculation are imminent. This cautionary note aside, nobody need worry about whether a credit card number is secure. The discovered method cannot be applied to breaking cryptographic codes.

This page intentionally left blank.