Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"Prime number puzzle solved at last," by Nicola Dixon. New Scientist, 11 August 2002, page 9.

This short article discusses the recent algorithm, developed by three computer scientists at the Indian Institute of Technology, that can factorize numbers into their prime factors within a reasonable amount of time. In computer science terms, this means the team has found a "polynomial-time" algorithm for factorizing numbers. Those problems for which polynomial-time algorithms are known to exist are in a class of problems called "P". The major outstanding question of theoretical computer science, the famous "P vs. NP" question, centers whether there are some problems for which such polynomial-time algorithms are not known. Computer scientists speculated that factorization was not in P, but until this latest discovery, no one knew for sure. Because the difficulty of factorization is the basis of many cryptographic systems, this new development could have ramifications for things like internet security; but, the article says, "Internet security is not yet under risk."

--- Allyn Jackson