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
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
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
In brief, there's a certain subclass of prime numbers known
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
big very fast. There's a nice table of the known Mersenne
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,
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
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?
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
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?
Actually, this is UCLA's eighth Mersenne Prime!
In 1952, Professor
Raphael Robinson found 5 new Mersenne Primes using
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?
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
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
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?
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?
There are lots of numbers of the form 2P-
only a very few of them are Mersenne Primes. There are a
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
is widely recognized as the best tool for testing Mersenne Primes.
The Prime95 program makes extensive use of this method, as
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?
the same reasons that people climb mountains, sail unknown
seas, and explore the cosmos. It's a challenge!
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
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?
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
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,
thought the informal competition between GIMPS sites would be
interesting for our students to follow, and increase their awareness of
Q. What did you
do to run this? Was it complicated?
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
Q. How does
a Mersenne Prime is found, a formal announcement is not
made until an independent third-party validates the claim.
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
Q. When did the
discovery occur? What kind of computer was used?
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?
Frontier Foundation (EFF), the Internet's premiere civil
liberties organization, sponsors the Cooperative Computing
These awards are intended to "encourage ordinary Internet
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
million digits, and meets the award criteria. Once the formal
are published in an appropriate journal, the prize will be awarded.
This will be in 2009 at the earliest.
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
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
Q. What's this I hear about a
poster? Will there be one for the UCLA Mersenne Prime?
For years, a company called Perfectly
has been creating a poster of the largest currently known explicit
prime number. The poster for M44, produced in 2006, used
extremely small typefont to squeeze 9.8 million digits onto a single
29" by 40" poster. The company offered a jeweler's loupe
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?
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,
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.