48th Mersenne Prime Computed 
Written by Mike James  
Friday, 08 February 2013  
Mersenne primes are easier to work with than general primes but the latest, the 48th known, has more than 17 million decimal digits  big by anyone's standards. A Mersenne prime is of the form 2^{p}1 and until recently we only knew of 47 of them. It can be shown that if p isn't itself a prime then 2^{p}1 can't be a prime, so some definitions include the condition that p is a prime. Certainly if you are looking for Mersenne primes you only need to test values of p that are prime. However, the problem isn't so much generating a possible Mersenne prime but in testing that it is a prime.
Marin Mersenne 15881648 The first few values of the form 2^{p}1 i.e. 3,7,31,127 are easy to prove as being prime because you can check them using division but larger values of p quickly generate very big numbers that would take too long to check by attempting division by all possible factors. The good news is that for a Mersenne prime there is a quick test called the Lucas–Lehmer primality test. This states that 2^{p}1 with p prime is only itself a prime if it divides M_{p2} where M_{p} is generated from the series S_{k}=S^{2}_{k1} 2 with S_{0}=4. As you can see this is much.easier task than testing all factors. In fact, it is so much easier than testing a general number for primality that the ten largest known primes are Mersenne primes. The latest was found by Curtis Cooper, a mathematician at the University of Central Missouri. He revealed the 48th Mersenne prime to be 2^{57,885,161}−1 (a number with decimal 17,425,170 digits), as a result of a search executed by a GIMPS server network. GIMPS, a distributed computing project designed to hunt for Mersenne primes, is also responsible for discovering the 10 largest Mersenne primes with the previous one, the 47th, being found in 2008. The GIMPS software runs on around 1000 University computers and proving that the current find was prime took one machine 39 days of computation. The proof was then checked on a 32core server in 6 days. The discovery is eligible for the $3,000 prize from the GIMPS Project, but it isn't big enough for the Electronic Frontier Foundation's prizes of $150,000 and $250,000 to the discovery of the first prime with at least 100 million and a billion digits, respectively. What is the point? Well if you are a mathematician you don't need a "point" that other people would understand. But there is something strange about the way that you can take 2 and multiply it by itself a few times to get what has to be a very factorable number and then taking one away from the result changes the pattern so much that we have a prime with no factors. It is also worth noting that, from a programming point of view, Mersenne primes are very simple. For example, in binary the first three are 11, 111, 11111 and so on. In general 2^{p}1 is just a binary number with p ones. The fact that we have Mersenne primes for p=31, 61 and 127 is often a very useful fact when you need a big prime number quickly. Finally, to prove that the 48th Mersenne prime isn't out of your reach Programming Praxis has a challenge and a solution for you  generate all 17 million plus digits. It turns out that simple C can't do it, but it is within the reach of the GNU Multiple Precision Arithmetic Library which gets there in a few minutes. 5 Trillion Digits of Pi  New world record Yahoo! Gets to the 2 Quadrillionth bit of Pi  it's zero 60 trillionth binary digit of pisquared calculated
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin, or sign up for our weekly newsletter.
Comments
or email your comment to: comments@iprogrammer.info


Last Updated ( Wednesday, 20 January 2016 ) 