Distributed computing strikes gold
A 20-year-old Canadian finds the world's largest known prime number using a mere desktop computer, but he wasn?t working alone.
- Shankland covered the tech industry for more than 25 years and was a science writer for five years before that. He has deep expertise in microprocessors, digital photography, computer hardware and software, internet standards, web technology, and more.
Using a computer with an 800MHz chip from Advanced Micro Devices, Michael Cameron found the prime number on Nov. 14, according to Entropia. The San Diego company sells software to enable "distributed computing," which harnesses the unused processing abilities of computers scattered across the Internet.
Although the arrival of profit motive has transformed distributed computing, its roots remain in academic pursuits such finding optimal Golomb rulers or alien radio signals.
Cameron's computer found the number, but he shares credit with others: George Woltman, who founded the Great Internet Mersenne Prime Search (GIMPS) and wrote the search software, and Entropia founder Scott Kurowski, who created the network system called PrimeNet that governs the 210,000 computers that are part of the effort.
Prime numbers, once a mathematical curiosity but now crucial to encrypted communications, are numbers greater than one that are divisible only by one and the number itself. Cameron was participating in a project to search for a particular type of prime number called a Mersenne prime.
The number that Cameron discovered--2 to the 13,466,917th power minus 1--has 4,053,946 digits. In order to cram his discovery onto a 29-inch-by-40-inch poster sold by Perfectly Scientific, the number is printed in a tiny 1.37-point font and read with a magnifying glass.
Mersenne primes are named after Marin Mersenne, a French monk born in 1588 who investigated a particular type of prime number: 2 to the power of "p" minus one, in which "p" is an ordinary prime number.
Mersenne primes are much rarer than ordinary primes. The GIMPS effort, exhaustively searching for possible candidates since 1996, has been responsible for discovering the five most recent examples. Altogether, 39 have been discovered so far.
Cameron's computer took 42 days to verify that the number was a Mersenne prime. After that, researchers using a workstation took three weeks to confirm the work.
Prime numbers are needed for encrypted communications such as a Web browser's Secure Sockets Layer (SSL) technology that makes it harder to sniff out credit card numbers or other private information. But those systems typically use primes that are merely 300 or so digits, said Stanford University mathematician Dan Boneh.
"The large Mersenne primes are not very useful," Boneh said, though finding one will grant a person 15 minutes of fame.
Mathematical hobbyists have provided online versions of Cameron's number written out in decimal form or in words.
Searching for Mersenne primes is computationally intense, but it is a problem that's known as "embarrassingly parallel," which means it can easily be broken down into independent parts that separate computers tackle. Many supercomputer problems take another form, requiring high-speed communication between separate computers or requiring that a problem be solved one step at a time with little opportunity for sharing among many systems.
Parallel computing tasks aren't merely academic. Sun Microsystems and Intel use distributed computing software to help design microprocessors, and companies such as Entropia, Turbolinux, Platform Computing, Parabon Computation and United Devices have software that can be used for work in genetics, pharmaceuticals or financial services. Typically, this software is used within a single corporation rather than on strangers' computers across the Internet.
The concept of distributed computing is closely related to "grid" computing, which unites computers and storage systems into a single pool of resources. The National Science Foundation is among those interested in the concept, devoting $53 million to one grid.
Entropia, IBM, Sun, Platform Computing and others are working with the open-source Globus Project to define standards and software for controlling grids.
Ultimately, researchers envision a future in which all computers are linked into a single mammoth resource that can be tapped when needed.
The Mersenne prime search is moving in that direction. Each day, its network of computers does work that would take a single 90MHz Pentium computer 200 years to accomplish. On average, the network of computers performs 2.4 trillion calculations per second.
The most popular model in the prime number hunt is a computer with an Intel Pentium III chip, with AMD Athlon chips coming in a close second.
Although the search effort is voluntary, there is an incentive to participate. The Electronic Frontier Foundation paid $50,000 to GIMPS participant Nayan Hajratwala of Plymouth, Mich., upon discovery of the first prime number with more than a million digits. Funded by an individual's specific donation, the organization also is offering $100,000 for the first 10 million digit prime, $150,000 for the first 100 million digit prime, and $250,000 for the first 1 billion digit prime.
Searchers are now looking for the 40th Mersenne prime. Software for the task can be downloaded from the Mersenne Web site.