The UCLA Mersenne Prime




In August of 2008, a new Mersenne Prime number was discovered on one of the computers belonging to the UCLA Mathematics Department's Program in Computing (PIC).  This number turns out to be the World's Largest known prime number, and the discovery has generated a lot of interest.  In an effort to save everyone time and energy, I thought I'd put some information up on the web in FAQ format.  

Since a number of the questions I've received have come from people with non-technical backgrounds (including children), this FAQ is non-technical.  You do have to know what a Prime Number is, though.  

I am compelled, though, to offer this caveat:  even though I work for the Mathematics Department, I'm a System Administrator, not a Mathematician!  If you're looking for serious Mersenne Prime information, I refer you to Chris Caldwell's excellent web site Mersenne Primes:  History, Theorems and Lists.  Other interesting sites include Wolfram's Mersenne Prime page and Landon Curt Noll's entertaining Mersenne Prime Digits and Names.

Now, on to the questions!




Q.  So what's a Mersenne Prime?

A.  In brief, there's a certain subclass of prime numbers known as Mersenne Primes.  They're named for Marin Mersenne, a 17th Century Mathematician.   At the time of this writing, there are fewer than 50 known Mersenne Primes.
 
Mersenne Prime numbers all take the form of
2P-1, where P is a known prime.  The first Mersenne Prime is 3  because 22 -1 = 3.  Note that the exponent P is a prime number, in this case 2.  The next Mersenne Prime is 7 because 23 - 1 = 7, with P being the prime number 3. Next comes 31 (25 - 1), then 127 (27 - 1), 8191 (213 - 1) and 131071 (217 - 1).

As you can see, after the first few, Mersenne Primes get big very fast. There's a nice table of the known Mersenne Primes here that will give some perspective.

The smallest of these numbers were known in antiquity, but as late as 1951 only 12 had been discovered.  Over the past 50 years, several dozen more have been uncovered with the help of computers.  The most recently discovered Mersenne Primes are staggeringly large, with millions of digits.  The UCLA Mersenne Prime is around 12.9 million digits in length.

Note that all Mersenne Primes are prime numbers, but very few prime numbers are Mersenne Prime numbers.


Q.  What's the UCLA Mersenne Prime?  Why is it special?

A.  The UCLA Mersenne Prime is the first prime discovered which has over 10 million digits.  It was discovered at the UCLA Mathematics department on August 23, 2008.  

All Mersenne Primes are special because they're so rare, but this one has gotten extra attention because it qualifies for a prize (see below).

The UCLA Mersenne Prime number is 243112609 - 1.  The actual number has 12,978,189 digits.  If you're so inclined, long-time Mersenne Prime researcher Landon Curt Noll has made the number itself available here.   If you're really, really inclined, he also provides the entire number in English (all 328 megabytes of it) here.   


Q.  Is this UCLA's first Mersenne Prime?

A.  Actually, this is UCLA's eighth Mersenne Prime!  

In 1952, Professor Raphael Robinson found 5 new Mersenne Primes using UCLA's Standards Western Automatic Computer (SWAC), one of the fastest computers of its time. These were the 13th through 17th Mersenne Primes discovered, and each had hundreds of digits.  Robinson's Mersenne Primes were the first to be found in 75 years, and the first to be discovered using a digital computer.

In 1961, UCLA mathematician Alexander Hurwitz discovered the 19th and 20th Mersenne Primes on the UCLA Computer Center's IBM 7090 mainframe.  Each of these numbers had over 1200 digits.

Now, 47 years later, the UCLA tradition of finding Mersenne Primes continues!


Q.  Who is looking for Mersenne Primes?  How are they going about it?

A.  Thousands of people using tens of thousands of computers are participating in the Great Internet Mersenne Prime Search (GIMPS), an organized effort dedicated to the search for Mersenne Primes.  This is one of many ongoing efforts in the field of distributed computing, and arguably the most successful.

The search is very well organized.  The good folks at Primenet have been coordinating the effort for the last 12 years, and provide the excellent Prime95 program free of charge to anyone who wants to run it.  They keep track of which numbers have been tested, and provide a steady stream of untested candidate numbers to the GIMPS community.  GIMPS participants are ranked according to their productivity
. You can find us under the name of UCLA_Math; we're typically ranked somewhere between 40th and 55th place.

It can take a single machine months to test just one candidate number, but by harnessing the power of Internet-connected individual computers all over the world, rapid progress can be made.


Q.  What are the odds of discovering a Mersenne Prime?

A.  According to the GIMPS project, the odds that any candidate number will turn out to be a Mersenne Prime are 1 in 150,000.


Q.  How do you actually test numbers to see if they're Mersenne Primes?

A.  There are lots of numbers of the form 2P- 1, but only a very few of them are Mersenne Primes.  There are a number of techniques to test these numbers to see if they're Mersenne Primes, but the initial method is to try to factor the candidate exponent, P, and then to try to factor the candidate prime, 2P-1, using some small primes.


There's a 75-year-old algorithm called the Lucas-Lehmer Test which is widely recognized as the best tool for testing Mersenne Primes.  The Prime95 program makes extensive use of this method, as well as some others.  An explanation is beyond the scope of this document, but the interested reader can learn more here.


Q.  OK, why are people looking for Mersenne Primes?  What are they good for?

A.  For the same reasons that people climb mountains, sail unknown seas, and explore the cosmos.   It's a challenge!  It's exciting to push the envelope of Computational Mathematics and to search for something unknown that you believe is out there.  As bonus, unlike the explorers of old, we get to sit in comfortable office chairs while we're searching!

This is not to say that there's no mathematical value in Mersenne Primes.  They're certainly of value in the field of cryptography, and may have other uses yet to be discovered.

Prime number researcher Chris Caldwell explores this issue in more depth in his article "Why do people find these primes?".


Q.  Aside from the challenge, why did you decide to participate?

A.  As has been the case at many other sites, we realized that our large (75 seat) PIC/Math Computer Lab was using only a fraction of its available CPU power.  Rather than let all those cycles go to waste, we looked at a number of distributed computing projects, determining
that GIMPS was the best fit for us.  In addition to the appropriateness of GIMPS being a Mathematics-based project, we found that it was very well-written and didn't interfere with the undergraduate computer users (this was not true of some of the other project software we investigated).

The Program in Computering (PIC) draws students from majors all over campus, so it was important to us that any lab-wide computing projects be comprehensible to all concerned.  GIMPS certainly fit the bill here, and as a bonus, we thought the informal competition between GIMPS sites would be interesting for our students to follow, and increase their awareness of Computational Mathematics.  


Q.  What did you do to run this?  Was it complicated?

A.  The GIMPS Prime95 software is very straightforward from a system administrative perspective.  It's easy to install, and doesn't require maintenance.  

The Prime95 software issues regular updates on its processing status to the central Primenet computers. If the machine its running on goes down, computations will start up again where they left off when the computer comes back up.  If an individual box is down for an extended period, Primenet will reclaim the number and assign it to someone else, and assign a new number when the machine returns to service.


Q.  How does verification work?

A.  When a Mersenne Prime is found, a formal announcement is not made until an independent third-party validates the claim.  With exceptionally large numbers such as these, there's always a small chance of a computational problem with the algorithm used, or with the CPU of the computer itself (the Intel Floating Point Problem is a classic example of this).  

Because of these potential problems, Mersenne Primes are always validated using a completely different algorithm on a computer with a different architecture.  Verification can take two weeks or longer.


Q.  When did the discovery occur?  What kind of computer was used?

A.  The UCLA Mersenne Prime was reported on August 23, 2008 on a computer named zeppelin.pic.ucla.edu, a Dell Optiplex 745 running Windows XP with an Intel Core 2 Duo E6600 CPU running at 2.4 GHz.  The name "zeppelin" was part of our Classic Rock Band series of computers.


Q.  What's all this about prize money?

A.  The Electronic Frontier Foundation (EFF), the Internet's premiere civil liberties organization, sponsors the Cooperative Computing Awards.  These awards are intended to "encourage ordinary Internet users to contribute to solving huge scientific problems," and feature prize money when certain benchmarks are achieved.

The EFF has a standing award of $100,000 for the first prime number with 10 million digits to be discovered.  The UCLA Mersenne Prime has almost 12.9 million digits, and meets the award criteria.  Once the formal results are published in an appropriate journal, the prize will be awarded.  This will be in 2009 at the earliest.

By pre-existing agreement, only 50% of the award will go to the discoverer of the 10 million digit prime.  25% is earmarked for charity, and in recognition of the collaborative nature of GIMPS, the bulk of the remaining 25% will go to the discoverers of other Mersenne Primes, with a small amount going to GIMPS itself.  


Q. What's this I hear about a poster?  Will there be one for the UCLA Mersenne Prime?

A.  For years, a company called Perfectly Scientific has been creating a poster of the largest currently known explicit prime number.  The poster for M44, produced in 2006, used an extremely small typefont to squeeze 9.8 million digits onto a single 29" by 40" poster.  The company offered a jeweler's loupe along with the poster just so it could be read.

Richard Crandall of Perfectly Scientific recently contacted me to let me know that the UCLA Mersenne Prime poster is now available for purchase.  It's $99, unframed, and available at the Perfectly Scientific web site.


Q. What about the other recently discovered Mersenne Prime?

A.  Two weeks after the UCLA Mersenne Prime was discovered, another 10 million digit plus Mersenne Prime was discovered by Hans-Michael Elvenich in Germany.  At 11.2 million digits, it's about 10% smaller than the UCLA Mersenne Prime.    


This is not the first time that Mersenne Primes have been discovered out of order.  In 1988, Colquitt and Welsh discovered a Mersenne Prime smaller than the previous two, discovered in 1983 and 1985.

At the time of this writing, the UCLA Mersenne Prime is the considered the 46th Mersenne Prime (called "M46" by the Mersenne Prime seeking community), even though it was the 45th discovered. Elvenich's Mersenne Prime is M45, but was the 46th discovered!

As a further complication, not all the potential primes between M39 (discovered in 2001) and the UCLA Mersenne Prime have been tested, so there could be more found in that range at a future date.  If they are, the UCLA Prime will get "promoted" to M47.



This FAQ is also available in the the Belarussian language, courtesy of Amanda Lynn.



I offer my heartfelt thanks to all the folks who helped me with this document.  Thank you to Sal Zapien and Mary Margaret Smith for their excellent proofreading, and to Jim Carter for his help with structure and organization.  I  especially wish to thank Robert Johnson, who made sure that each and every statement I made was factual, and who gently corrected my numerous misconceptions.

This FAQ created and maintained by Edson Smith.  Last update March, 2009.