Science

The Largest Known Prime Number

It’s 23,249,425 digits long. That’s incredibly exciting.

numbers promo.
RSA encryption, one of the standard ways to scramble data online, requires the user to come up with two big primes and multiply them together.

Eyematrix/Thinkstock

Update, Jan. 4, 2018: On Wednesday, the Great Internet Mersenne Prime Search announced that a computer owned by Jonathan Pace in Germantown, Tennessee, discovered a new prime number. At 23,249,425 digits, the number, known as M77232917, is now the largest known prime.

In 2016, I wrote the following article about the previous largest known prime, which is now the second largest known prime. Its name is M74207281, and it’s about a million digits shorter than the shiny new prime. But other than a few details about whose computer found it and exactly how long it is, I could have written this article today about the new prime. So we’re sharing it with you again.

It’s exciting to find a new largest known prime number, but this is another verse of the same song. Both numbers, like nine of the 10 largest known prime numbers, have a special form and are called Mersenne primes. We find them because that’s where we keep looking. The light is better there. Between these two largest known primes lie an unfathomable number of monstrously large primes; we may never find even one.

Original, Jan. 22, 2016: 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.

The heat death of the universe would occur before we could get even a fraction of the way through trial division of a number with 22 million digits. It only took a month, however, for a computer to use the Lucas-Lehmer test to determine that M74207281 is prime. There are no other primality tests that run nearly as quickly for arbitrary 22 million–digit numbers.

How many primes have we missed by looking for them mostly under the Lucas-Lehmer street lamp? We don’t know the exact answer, but the prime number theorem gets us close enough. It makes sense that primes get less common as we stroll out on the number line. Fully 40 percent of one-digit numbers are prime, 22 percent of two-digit numbers are prime, and only 16 percent of three-digit numbers are. The prime number theorem, first proved in the late 1800s, quantifies that decline. It says that in general, the number of primes less than n tends to n/ln(n) as n increases. (Here ln is the natural logarithm.)

We can use the prime number theorem to estimate how many missing primes there are between M74207281 and the next smallest prime. We just plug 274,207,281-1 into n/ln(n) and get, well, a really big number. We can write it most compactly by stacking exponents: 10107.349. This number has about 22,338,610 digits, give or take a couple, so we can also write it as 1022,338,610.

Another visit to the prime number theorem shows there are approximately 1017,425,163 primes less than the next-largest known prime. That sounds impressive until you realize 1017,425,163 is less than 0.000000000001 percent of 1022,338,610.

Stop and think about that for a moment. There are about 1022,338,610 primes less than M74207281, and approximately all of them are between it and the next-largest known prime. If you want to be charitable, you could say we have some gaps in our knowledge of prime numbers. But really, it makes more sense to say we have gaps in our lack of knowledge. The millions upon millions of prime numbers we’ve already found make up approximately 0 percent of the primes that are less than M74207281. Each one is a little grain of sand, a speck that does little to cover up our overwhelming ignorance of exactly where the prime numbers live.

Correction, Jan. 22, 2016: This story originally referred to a possible prime number as 2n-1. That number should have been rendered as 2n-1. (Return.)