The world’s largest prime number has 22,338,618 digits. Here’s why you should care.

Why You Should Care About a Prime Number That’s 22,338,618 Digits Long

The state of the universe.
Jan. 22 2016 3:54 PM

The Largest Known Prime Number

It’s 22,338,618 digits long. That’s incredibly exciting.

Earlier this week, BBC News reported an important mathematical finding, sharing the news under the headline “Largest Known Prime Number Discovered in Missouri.” That phrasing makes it sound a bit like this new prime number—it’s 274,207,281-1, by the way—was found in the middle of some road, underneath a street lamp. That’s actually not a bad way to think about it.

We know about this enormous prime number thanks to the Great Internet Mersenne Prime Search. The Mersenne hunt, known as GIMPS, is a large distributed computing project in which volunteers run software to search for prime numbers. Perhaps the best-known analogue is SETI@home, which searches for signs of extraterrestrial life. GIMPS has had a bit more tangible success than SETI, with 15 primes discovered so far. The shiny new prime, charmingly nicknamed M74207281, is the fourth found by University of Central Missouri mathematician Curtis Cooper using GIMPS software. This one is 22,338,618 digits long.

A prime number is a whole number whose only factors are 1 and itself. The numbers 2, 3, 5, and 7 are prime, but 4 is not because it can be factored as 2 x 2. (For reasons of convenience, we don’t consider 1 to be a prime.) The M in GIMPS and in M74207281 stands for Marin Mersenne, a 17th-century French friar who studied the numbers that bear his name. Mersenne numbers are 1 less than a power of 2. Mersenne primes, logically enough, are Mersenne numbers that are also prime. The number 3 is a Mersenne prime because it’s one less than 22, which is 4. The next few Mersenne primes are 7, 31, and 127.

M74207281 is the 49th known Mersenne prime. The next largest known prime, 257,885,161-1, is also a Mersenne prime. So is the one after that. And the next one. And the next one. All in all, the 11 largest known primes are Mersenne.

Why do we know about so many large Mersenne primes and so few large non-Mersenne ones? It’s not because large Mersenne primes are particularly common, and it’s not a spectacular coincidence. That brings us back to the road and the street lamp. There are several different versions of the story. A man, perhaps he’s drunk, is on his hands and knees underneath a streetlight. A kind passerby, perhaps a police officer, stops to ask what he’s doing. “I’m looking for my keys,” the man replies. “Did you lose them over here?” the officer asks. “No, I lost them down the street,” the man says, “but the light is better here.”

We keep finding large Mersenne primes because the light is better there.

First, we know that only a few Mersenne numbers are even candidates for being Mersenne primes. The exponent n in 2n-1 needs to be prime, so we don’t need to bother to check 26-1, for example.* There are a few other technical conditions that make certain prime exponents more enticing to try. Finally, there’s a particular test of primeness—the Lucas–Lehmer test—that can only be used on Mersenne numbers.

To understand why the test even exists, let’s take a detour to explore why we bother finding primes in the first place. There are infinitely many of them, so it’s not like we’re going to eventually find the biggest one. But aside from being interesting in a “math for math’s sake” kind of way, finding primes is good business. RSA encryption, one of the standard ways to scramble data online, requires the user (perhaps your bank or Amazon) to come up with two big primes and multiply them together. Assuming the encryption is implemented correctly, the difficulty of factoring the resulting product is the only thing between hackers and your credit card number.

This new Mersenne prime is not going to be used for encryption any time soon. Currently we only need primes that are a few hundred digits long to keep our secrets safe, so the millions of digits in M74207281 are overkill, for now.

You can’t just look up a 300-digit prime in a table. (There are about 10297 of them. Even if we wanted to, we physically could not write them all down.) To find large primes to use in RSA encryption, we need to test randomly generated numbers for primality. One way to do this is trial division: Divide the number by smaller numbers and see if you ever get a whole number back. For large primes, this takes way too long. Hence there are primality tests that can determine whether a number is prime without actually factoring it. The Lucas-Lehmer test is one of the best.