PRIME NUMBER :
A prime number is a whole number greater than 1 whose on
ly factors are 1 and itself.
the search for ever-larger primes has long occupied maths enthusiasts.
However, the search requires complicated computer software and collaboration as the numbers get increasingly hard to find.
A collaborative computational effort has uncovered the longest known prime number.
M77232917 was discovered on a computer belonging to Jonathan Pace, an electrical engineer from Tennessee who has been searching for big primes for 14 years.
Mr Pace discovered the new number as part of the Great Internet Mersenne Prime Search (GIMPS), a project started in 1996 to hunt for these massive numbers.
Six days of non-stop computing in which 77,232,917 twos were multiplied together resulted in the latest discovery.
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.
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.
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.
For More Information on Mersenne Primes
Prime numbers have long fascinated amateur and professional mathematicians. An integer greater than one is called a prime number if its only divisors are one and itself. The first prime numbers are 2, 3, 5, 7, 11, etc. For example, the number 10 is not prime because it is divisible by 2 and 5. A Mersenne prime is a prime number of the form 2P-1. The first Mersenne primes are 3, 7, 31, and 127 corresponding to P = 2, 3, 5, and 7 respectively. There are only 49 known Mersenne primes.
Mersenne primes have been central to number theory since they were first discussed by Euclid about 350 BC. The man whose name they now bear, the French monk Marin Mersenne (1588-1648), made a famous conjecture on which values of P would yield a prime. It took 300 years and several important discoveries in mathematics to settle his conjecture.
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 number
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
About Mersenne.org's Great Internet Mersenne Prime Search
The Great Internet Mersenne Prime Search (GIMPS) was formed in January 1996 by George Woltman to discover new world record size Mersenne primes. In 1997 Scott Kurowski enabled GIMPS to automatically harness the power of hundreds of thousands of ordinary computers to search for these "needles in a haystack". Most GIMPS members join the search for the thrill of possibly discovering a record-setting, rare, and historic new Mersenne prime. The search for more Mersenne primes is already under way. There may be smaller, as yet undiscovered Mersenne primes, and there almost certainly are larger Mersenne primes waiting to be found. Anyone with a reasonably powerful PC can join GIMPS and become a big prime hunter, and possibly earn a cash research discovery award.
Dr. Cooper is a professor at the University of Central Missouri. This is the fourth record GIMPS project prime for Dr. Cooper and his university. The discovery is eligible for a $3,000 GIMPS research discovery award. Their first record prime was discovered in 2005, eclipsed by their second record in 2006. Dr. Cooper lost the record in 2008, reclaimed it in 2013, and improves that record with this new prime. Dr. Cooper and the University of Central Missouri is the largest contributor of CPU time to the GIMPS project.
Dr. Cooper's computer reported the prime in GIMPS on September 17, 2015 but it remained unnoticed until routine maintenance data-mined it. The official discovery date is the day a human took note of the result. This is in keeping with tradition as M4253 is considered never to have been the largest known prime number because Hurwitz in 1961 read his computer printout backwards and saw M4423 was prime seconds before seeing that M4253 was also prime.
GIMPS Prime95 client software was developed by founder George Woltman. Scott Kurowski wrote the PrimeNet system software that coordinates GIMPS' computers. Aaron Blosser is now the system administrator, upgrading and maintaining PrimeNet as needed. Volunteers have a chance to earn research discovery awards of $3,000 or $50,000 if their computer discovers a new Mersenne prime. GIMPS' next major goal is to win the $150,000 award administered by the Electronic Frontier Foundation offered for finding a 100 million digit prime number.
Credit for GIMPS' prime discoveries goes not only to Dr. Cooper for running the Prime95 software on his university's computers, Woltman, Kurowski, and Blosser for authoring the software and running the project, but also the thousands of GIMPS volunteers that sifted through millions of non-prime candidates. Therefore, official credit for this discovery shall go to "C. Cooper, G. Woltman, S. Kurowski, A. Blosser, et al."
Previous GIMPS Mersenne prime discoveries were made by members in various countries.
In January 2013, Curtis Cooper et al. discovered the 48th known Mersenne prime in the U.S.
In April 2009, Odd Magnar Strindmo et al. discovered the 47th known Mersenne
prime in Norway.
In September 2008, Hans-Michael Elvenich et al. discovered the 46th known Mersenne prime in Germany.
In August 2008, Edson Smith et al. discovered the 45th known Mersenne prime in the U.S.
In September 2006, Curtis Cooper and Steven Boone et al. discovered the 44th known Mersenne prime in the U.S.
In December 2005, Curtis Cooper and Steven Boone et al. discovered the 43rd known Mersenne prime in the U.S.
In February 2005, Dr. Martin Nowak et al. discovered the 42nd known Mersenne
prime in Germany.
In May 2004, Josh Findley et al. discovered the 41st known Mersenne prime in the U.S.
In November 2003, Michael Shafer et al. discovered the 40th known Mersenne prime in the U.S.
In November 2001, Michael Cameron et al. discovered the 39th Mersenne prime in Canada.
In June 1999, Nayan Hajratwala et al. discovered the 38th Mersenne prime in the U.S.
In January 1998, Roland Clarkson et al. discovered the 37th Mersenne prime in the U.S.
In August 1997, Gordon Spence et al. discovered the 36th Mersenne prime in the U.K.
In November 1996, Joel Armengaud et al. discovered the 35th Mersenne prime in France.
Euclid proved that every Mersenne prime generates a perfect number. A perfect number is one whose proper divisors add up to the number itself. The smallest perfect number is 6 = 1 + 2 + 3 and the second perfect number is 28 = 1 + 2 + 4 + 7 + 14. Euler (1707-1783) proved that all even perfect numbers come from Mersenne primes. The newly discovered perfect number is 274,207,280 x (274,207,281-1). This number is over 44 million digits long! It is still unknown if any odd perfect numbers exist.
There is a unique history to the arithmetic algorithms underlying the GIMPS project. The programs that found the recent big Mersenne finds are based on a special algorithm. In the early 1990's, the late Richard Crandall, Apple Distinguished Scientist, discovered ways to double the speed of what are called convolutions -- essentially big multiplication operations. The method is applicable not only to prime searching but other aspects of computation. During that work he also patented the Fast Elliptic Encryption system, now owned by Apple Computer, which uses Mersenne primes to quickly encrypt and decrypt messages. George Woltman implemented Crandall's algorithm in assembly language, thereby producing a prime-search program of unprecedented efficiency, and that work led to the successful GIMPS project.
School teachers from elementary through high-school grades have used GIMPS to get their students excited about mathematics. Students who run the free software are contributing to mathematical research. David Stanfill's verification computation for this discovery was donated by Squirrels (airsquirrels.com) which services K-12 education and other customers.
