The Great Internet Mersenne Prime Search, a cooperative computing project, helps find a prime that has nearly 13 million digits.

By Julie Rehmeyer

Web edition: September 23, 2008

Here’s a number to savor: 2^43,112,609-1.

Its size is mind-boggling. With nearly 13 million digits, it makes the number of atoms in the known universe seem negligible, a mere 80 digits.

And its form is tidy and lovely: 2ⁿ-1.

But its true beauty is far grander: It is a prime number. Indeed, it is the largest prime number ever found.

The Great Internet Mersenne Prime Search, or GIMPS, a computing project that uses volunteers’ computers to hunt for primes, found the prime and just confirmed the discovery. It can now claim a $100,000 prize from the Electronic Frontier Foundation for being the first to find a prime number that has more than 10 million digits.

Prime numbers make up the “periodic table” of numbers, the building blocks that combine to form all numbers. A prime number is a whole number divisible only by 1 and itself. Euclid in 300 B.C. proved that there are infinitely many of them (click for his beautifully simple proof). Still, that doesn’t make them easy to find. At the beginning of the number line, the primes seem to be everywhere — 2, 3, 5, 7, 11, 13… — but in the number line’s more distant reaches, prime numbers become elusive.

Because 2^43,112,609-1 has the form 2ⁿ-1, it’s called a “Mersenne prime,” after a French monk born in the 16^th century who made an (incorrect) conjecture about them. Mersenne primes are of particular interest partly because they can be expressed in such a compact form. (It sure is easier to write 2^43,112,609-1 than to type out all 13 million digits!) More significantly, though, some clever methods have been developed to identify them.

The most obvious way to go about identifying any prime number is to try factoring it. First, try dividing by 3, then 5, then 7, etc., and if none of them work, you’ve got a prime. But the last time a new prime was identified this way was in 1588, because as the numbers get bigger, the division takes longer and longer. So mathematicians have developed clever tests for primeness that are simpler to compute. The best one of all, called the Lucas-Lehmer test, only works for Mersenne primes. Remarkably, the method requires no division at all, making it extremely quick.

Only 46 Mersenne primes have ever been found, and GIMPS has found 12 of them. The project recruits volunteers to donate their computers’ CPU cycles when they would otherwise be idle. Each computer works on a single number, first trying to find small factors. If that fails, it applies the Lucas-Lehmer test. A computer working full-time can test a single 10-million-digit number in eight days.

The processing power of all the individual computers linked together is equivalent to one of the most powerful supercomputers in the world. No supercomputer, though, would devote all its processing time to computing prime numbers.

The finding is unlikely to have significance for number theory, although number theory’s great unanswered question, perhaps, is to find how the prime numbers are distributed. Still, “you never know where discoveries may lead you,” says George Woltman, founder of GIMPS. “But really, it’s like climbing Mt. Everest. You do it because it’s there. It’s a lot safer, though. You can do it from the air-conditioned comfort of your home.”

Or, if you prefer, the air-conditioned comfort of your office. The computer that found the prime was administered by Edson Smith at the University of California, Los Angeles mathematics department. Smith downloaded the GIMPS software, and when the computers in the math department weren’t busy with other work, they searched for primes and communicated their results back to GIMPS.

This prime is the eighth found at UCLA, although the first with GIMPS. Half the prize money will go to the UCLA math department, a quarter will go to charity (probably a math department with an open faculty position for number theory, Woltman says) and most of the remainder will go to those who found previous Mersenne primes using GIMPS.

Remarkably, GIMPS found another Mersenne prime two weeks after this one – after a two-year dry spell with no new primes. This prime had fewer digits, just 11 million.

The Electronic Frontier Foundation became interested in prime hunting because it makes an excellent challenge problem for cooperative, distributed computing. “The award is an incentive to stretch the computational ability of the Internet,” says Landon Noll of Cisco Systems Inc., one of the judges for the Electronic Frontier Foundation prize and a discoverer of a former biggest known prime. More prizes remain to be claimed: a $150,000 award for a prime with 100 million digits, and a $250,000 award for one with a billion digits.

GIMPS has used well-established methods, while continuing to refine its implementations for greatest efficiency. Finding the numbers for the larger awards, though, will require major innovations, Noll says: “People are going to have to go back to the drawing board.” He points out that testing a single 100-million–digit number for primeness would take a single desktop computer more than four years, and testing a billion-digit number would take it more than 500 years. So at a minimum, he says, algorithms will have to be developed that allow multiple computers to test a single prime.

Current cryptographic systems rely on the challenge of factoring large primes. This task is distinct from verifying primeness, but the root difficulty is the same: limited computing power. Through this prize, “we maintain a pulse on what people might be able to do in breaking cryptosystems,” Noll says.