Technology

mersenne prime, largest prime number
Marin Mersenne

13 Million-Digit Prime Number Shows Benefits of Distributed Computing Projects

October 01, 2008 02:45 PM
by Denis Cummings
The mathematics department at UCLA discovered a 12,978,189-digit prime number using a “grassroots supercomputer” of 100,000 computers worldwide.

GIMPS Discovers New Mersenne Primes

facebook
Two new prime numbers, the first two over 10 million digits long, have been discovered in the past two months. On August 23, the UCLA Math Department, led by systems administrator Edson Smith, discovered a 12,978,189- digit prime number and just two weeks later, German engineer Hans-Michael Elvenich discovered an 11,185,272-digit prime number. The numbers were just the 45th and 46th Mersenne prime numbers ever discovered, and the first since 2006.

Both numbers were discovered using the software of the Great Internet Mersenne Prime Search (GIMPS), a worldwide network of roughly 100,000 computers. GIMPS brings together thousands of small departments and individual volunteers to run GIMPS software on their computers, combining to form a system that would be too cost-prohibitive for a single company to create.

“There are so few of this-large prime numbers,” said Smith. “They’re very rare and can only be discovered through computing power. It’s really about the power of the grid .”

For its discovery, UCLA and GIMPS will share a $100,000 prize given by the Electronic Frontier Foundation, an online civil liberties group.  It is also offering a $150,000 and $250,000 prize for the discovery of the first 100-million-digit and one-billion-digit prime number.

“EFF hopes to spur the technology of cooperative networking and encourage Internet users worldwide to join together in solving scientific problems involving massive computation,” says the organization on its Web site.

Similar distributed computing projects are being used in many mathematical, scientific and health fields. Prominent projects include the study of proteins by Folding@home and Rosetta@home, the study of climate change at Climateprediction.net, and the “Search for Extra-Terrestrial Intelligence” at UC Berkeley’s SETI@home.
The success of the GIMPS project shows the value of such projects. “Prime numbers are important in mathematics and encryption,” says EFF co-founder David Gilmore, “but the real message is that many other problems can be solved by similar methods.”

Background: Prime numbers and their importance

A prime numbers is a number that can be divided by only two positive integers: one and itself. The numbers discovered by GIMPS are Mersenne primes, which are derived from an equation studied by French monk Marin Mersenne in the 17th century. The equation is two to the power of P, minus one, where P is a prime number.

For example, the first Mersenne prime number is two raised to the power of two minus one, which equals three. In the number discovered at UCLA, P=43,112,609, and in the number discovered in Germany, P= 37,156,667. It was originally believed that the equation would yield prime numbers for each P, but that theory was disproved in 1536.

Just 12 Mersenne primes had been discovered before 1952, when Berkeley professor Raphael Robinson discovered five using UCLA’s Standards Western Automatic Computer. Seventeen more were discovered before the launch of GIMPS in 1996. GIMPS has been responsible for the last 12 Mersenne primes found.

For many years, the study of prime numbers was considered to have no practical purpose. However, prime numbers are used in encryption and are valuable in creating Internet security systems.

“Each website has a public code number which is used to encode credit-card numbers,” writes mathematics professor Marcus du Sautoy in The Times of London. “To decode these secret messages a hacker must find the two primes that are multiplied together to give the website’s public code number. Unsurprisingly, the websites are using numbers with several hundred digits that are virtually impossible to crack into primes.”
facebook

Most Recent Beyond The Headlines