the great prime Mersenne.

Computer lab team hits its prime

Now that we've all had time to adjust to the enormity of $700 billion, here's a new challenge: Try bending your mind around a number that's 13 million digits long.

It's a number that is so long that if you typed it out at 10 characters per inch, it would stretch 20 to 30 miles long, depending on what font you were using. As the world's largest known prime number (a number only divisible by itself and 1), it was recently discovered by an ordinary UCLA computer in the math department, thanks to the efforts of a team of seven system administrators who joined a competition called the Great Internet Mersenne Prime Search (GIMPS) a year ago.


UCLA's prime team includes (eft to right)Charles Chen,Chris Oberlander, Jim Carter,Edson Smith,Robert Amodeo and Ed Trejo. Missing from the photo is Linda Bingham. (Photo by Reed Hutchinson)
Last August, the team leader, computing resource manager Edson Smith, went down in history as the finder of the 45th known Mersenne Prime (MP), ending a nearly decades-long hunt by more than 50,000 people and tens of thousands of computers around the world. Once the number is published a year from now in some academic journal, Smith is likely to share in a $100,000 prize. The money is being provided by the Electronic Frontier Foundation — the Internet's premier civil liberties organization — to the finder of the first Mersenne Prime that is at least 10 million digits long.

Under the rules, 50 percent of the award will go to the finder of the number, with 25 precent going to charity (budget-strapped math departments qualify) and 25 percent going to the other discoverers of MPs. GIMPS will also receive a small slice of the award.

"We didn't really do this for the money," said Smith, sitting amidst 75 computers in Boelter Hall's Program In Computing (PIC) Lab, where the UCLA hunt-for-the-prime was based. "It was more of an exercise that we thought would be fun and maybe get undergrads interested in computational math. It's a hobby for some people, sort of a passion. There's really no guarantee that any of these numbers exist. We don't know they're there until we find them. So it's exciting to push the envelope."

The power of many

The Mersenne Primes, named after 17th century mathematician and music theorist Marin Mersenne, are a subclass of prime numbers that can be expressed mathematically as 2p-1.(In this case, the UCLA exponent, the p, is a whopping 43,112,609.) While ancient mathematicians found the smaller MPs by doing their own calculations, the MPs quickly got larger and more unwieldy. The majority of MPs have been discovered in the past 50 years, largely with the help of computers and several of them at UCLA. UC Berkeley professor Raphael Robinson, while on temporary assignment at UCLA, found five MPs in 1952 using one of the fastest computers of that era. In 1961, Alexander Hurwitz, a UCLA mathematician, discovered two MPs on another UCLA computer.

In fact, tens of thousands have participated in the search by downloading a free program from GIMPS, which keeps track of which numbers are tested and eliminated, and sends out untested candidate numbers to the GIMPS community for factoring. The process of factoring one number can take a computer as long as two months, Smith explained. But joining forces via the Internet makes the search possible.

"It's an example," Smith said, "of the power of distributed computing," leveraging the power of Internet-connected computers all over the world.


The first few digits of the Mersenne prime number discovered at UCLA.
The ability to exploit the power of many computers working in parallel could, in fact, have an additional significant side benefit, said Terence Tao, UCLA's first mathematician to receive the prestigious Fields Medal, often described as the "Nobel Prize in Mathematics."

"This could very well come in handy for any future mathematical problem which requires a similar amount of manipulation of extremely large numbers," Tao noted. "In particular, the type of computations that come up in modern cryptography are actually quite similar in many ways to what is used by GIMPS. So there may be some insights gained into how to encrypt or decrypt messages more quickly."

Humble lab, newfound celebrity

The MP discovery has given the humble PIC Lab some notoriety. "Welcome to the world famous PIC Lab" a handwritten sign on the door says. "Big Number Found Here," another hand-lettered sign announces. Located way, way off the beaten path in Boelter Hall, the lab is used by non-computer science majors from north and south campus who learning computer programming.

But when the students leave and the computers are left to their own devices, their unused power, their CPUs, are left unengaged — at least until about a year ago, when they joined the quest for the MP.

"We knew we had lots and lots of computers down here that weren't doing anything 99.9 percent of the time," Smith said. "They were just running idle. And we were looking for something useful for them to do."

Smith's team, whose members do everything from build computer clusters to deal with dirty "mice," looked at several distributed computing projects that could run on PIC computers in the background when there was downtime. They decided to load the GIMPS program because it's simple, well written and doesn't interfere with the computers' main job. They also hoped that students might become interested in the challenge and learn more about computational math.


Learn more about Mersenne Primes with this FAQ put together by Smith for both the math- inclined and the math-challenged.

"When we did this, we never expected to actually find one," Smith said. But on August 23, a Dell Optiflex 745 running Wondows XP started inexplicably beeping. "I thought it might be broken. It was making the same sound you get with a broken keyboard," said Smith.

But an e-mail from George Woltman, who founded GIMPS and wrote the prime testing software, confirmed that he had received a message — one of the UCLA computers had indeed turned up a candidate prime.

GIMPS tested the number by factoring it using a different algorithm on various kinds of computers. "We had to sweat it out for two weeks until they verified it," Smith said.

Oddly enough, two weeks after the UCLA prime was discovered, Hans-Michael Elvenich of Germany, another prime number enthusiast, came up with an MP — but only 11.2-million digits long, smaller than UCLA's.


Learn more about the Great Internet Mersenne Prime Search.

Since their find was made public, Smith has been interviewed by the L.A. Times, Australian and BBC radio and the Voice of America. "I'm not a mathematician," he tells them repeatedly, slightly uncomfortable with his newfound celebrity.

It's not what one man — or even one computer — can do, Smith reminds people.

"The most important thing is that we are pushing the frontiers of what cooperative computers can do," he said. "People working together on a single goal can solve amazing things that are completely unsolvable without cooperation."

source : http://www.today.ucla.edu/portal/ut/PRN-081008_mersenne-prime.aspx