GIMPS: The Great Internet Mersenne Prime Search

The GIMPS Logo. Public domain, via Wikimedia Commons.

The GIMPS Logo. Public domain, via Wikimedia Commons.

Approximately two years ago, I decided to build my first desktop. From browsing various forums on the internet, I learned that many PC builders would run their hardware at higher speeds for more performance than the manufacturers specify when selling components. However, when doing this, one must run a program that uses 100% of a processor’s computing power to ensure the stability of the PC so that it will not shut down or encounter a Blue Screen of Death while playing video games or doing other important work. It was in this situation that I first encountered a program known as Prime95.

Prime95, in addition to being used to test overclocked processors, is used by the members of The Great Internet Mersenne Prime Search, or GIMPS, to search for large Mersenne primes.

Mersenne numbers have the form 2n-1, where n is a positive integer. Mersenne primes are those Mersenne numbers that are prime; the first four are 22-1, 23-1, 25-1, and 27-1. These special primes are named for the French theologian and mathematician Marin Mersenne. Born in 1588 in Oizé, France, Mersenne was always interested in studying mathematics, and published a paper in 1644 that included a statement about numbers of the form 2n-1. He claimed that for n less than 257, the values n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 made the number prime. However, Mersenne admitted to not having tested all of the positive integers less than 257. With the use of many mathematical discoveries, it was shown that n = 67 and 257 did not make 2n-1 prime, and that n = 61, 89, and 107 also made it prime, making a total of five errors in Mersenne’s list for n < 257. This led to many individuals becoming interested in finding large Mersenne primes.

GIMPS was founded in 1996 by George Woltman, who graduated from MIT with a Master’s degree in Computer Science. GIMPS and Prime95 use a method to perform calculations known as “distributed computing.” Distributed computing is essentially an alternative to using supercomputers to perform difficult calculations – instead of using a small number of supercomputers to solve problems, people around the world “donate” time when their computer is not being used to work on small chunks of these large calculations.

Since 1996, Prime95 has been used to discover fourteen Mersenne Primes. The first of these was in November of the year GIMPS was founded, 21,398,269-1. On January 25th, 2013, the 48th known Mersenne prime was discovered, 257,885,161-1. On February 24th of this year (2014), it was verified that the 43rd known Mersenne prime, 230,402,457-1, was, in fact, the 43rd Mersenne prime, meaning that we know of every Mersenne prime smaller than this 43rd one, and there are exactly 42 Mersenne primes that are smaller.

How does GIMPS discover these large primes? Prime95 uses a method known as the Lucas-Lehmer Primality test, a recursive relation, to determine whether a Mersenne number (Mn = 2n – 1) is prime or not. If it is prime, it is therefore a Meresnne prime (Mp = 2p – 1) where n=p. The Lucas-Lehmer test uses the following relation:

sn ≡ (sn-1)2-2 mod Mn.

where s0 ≡ 4. The Lucas-Lehmer residue, sn-2 mod Mn, determines whether a Mersenne number is prime; a Mersenne number is prime if and only if the Lucas-Lehmer residue is congruent to 0 mod Mn.

If, for example, we want to determine whether the Mersenne number 211-1 is a prime, then p = 11 and M11 = 2047. We therefore need to find the Lucas-Lehmer residue, s9, to determine whether M11 is a Mersenne prime.

The first index is always congruent to 0, so we start with:
s0 ≡ 4 mod M11.

We then calculate the second residue using the formula.
s1 ≡ sn-12-2 mod M11 ≡ s02-2 mod M11.

Since s0 ≡ 4 mod M11:
s02 – 2 mod M11 ≡ 16-2 mod M11.

Which is then congruent to:
16-2 mod M11 ≡ 14 mod M11.

Therefore, our second residue s1 is:
s1 ≡ 14 mod M11.

We then use this second residue to calculate our third residue s2.
s2 ≡ s22-2 mod M11 ≡ 194 mod M11.

We then continue to use this formula to calculate the next six residues:

s3 ≡ 788 mod M11.
s4 ≡ 701 mod M11.
s5 ≡ 119 mod M11.
s6 ≡ 1877 mod M11.
s7 ≡ 240 mod M11.
s8 ≡ 282 mod M11.

We can now finally calculate s9, the Lucas-Lehmer residue. This tenth residue turns out to be:
s9 ≡ 1736 mod M11.

Because the Lucas-Lehmer residue must be congruent to 0 mod M11 for M11 to be a Mersenne prime, the Mersenne number M11 = 2047 is not a Mersenne prime, which matches GIMPS’ own list of the 48 known Mersenne primes.

While the search for these large primes may not seem particularly relevant at first, there is one important application: RSA encryption. In RSA encryption, a user can post a “public key” which is the product of two extremely large primes. A message can be encrypted to that user with the public key, but for the message to be decrypted, the public key has to be factored into the exact two primes used to get it. This is an extremely time consuming and difficult feat to accomplish – unless you happen to know what those two primes are. This makes large primes extremely effective in encryption, the most prevalent use of large primes in our world today. Click here for more information on RSA encryption.

The Great Internet Mersenne Prime Search has generated many primes with their distributed computing program Prime95, which primarily uses the Lucas-Lehmer primality test to test large Mersenne numbers. If you want to join in the search for the next Mersenne prime, you can sign up at http://www.mersenne.org and download Prime95.

But don’t try computing these by hand with a calculator. M48 is 17.4 million digits long.

Sources:

http://mathworld.wolfram.com/Lucas-LehmerTest.html

http://www.mersenne.org/

http://www.bacchae.co.uk/docs/dist.html

http://primes.utm.edu/bios/page.php?lastname=Woltman

http://primes.utm.edu/glossary/page.php?sort=MersennesConjecture

http://www-history.mcs.st-andrews.ac.uk/Biographies/Mersenne.html

http://arstechnica.com/science/2013/02/ask-ars-why-spend-time-and-money-finding-new-prime-numbers/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s