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 *2 ^{n}-1*, where n is a positive integer. Mersenne primes are those Mersenne numbers that are prime; the first four are

*2*,

^{2}-1*2*,

^{3}-1*2*, and

^{5}-1*2*. 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

^{7}-1*2*. 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

^{n}-1*2*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.

^{n}-1GIMPS 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, *2 ^{1,398,269}-1*. On January 25th, 2013, the 48th known Mersenne prime was discovered,

*2*. On February 24th of this year (2014), it was verified that the 43rd known Mersenne prime,

^{57,885,161}-1*2*, 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.

^{30,402,457}-1How 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 *(M _{n} = 2^{n} – 1)* is prime or not. If it is prime, it is therefore a Meresnne prime

*(M*where n=p. The Lucas-Lehmer test uses the following relation:

_{p}= 2^{p}– 1)*s _{n} ≡ (s_{n-1})^{2}-2 mod M_{n}.*

where *s _{0} ≡ 4*. The

*Lucas-Lehmer residue,*

*s*, 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 M

_{n-2}mod M_{n}_{n}.

If, for example, we want to determine whether the Mersenne number *2 ^{11}-1* is a prime, then

*p = 11*and

*M*. We therefore need to find the Lucas-Lehmer residue,

_{11}= 2047*s*, to determine whether

_{9}*M*is a Mersenne prime.

_{11}The first index is always congruent to 0, so we start with:

*s _{0} ≡ 4 mod M_{11}.*

We then calculate the second residue using the formula.

*s _{1} ≡ s_{n-1}^{2}-2 mod M_{11} ≡ s_{0}^{2}-2 mod M_{11}.*

Since *s _{0} ≡ 4 mod M_{11}*:

*s*

_{0}^{2}– 2 mod M_{11}≡ 16-2 mod M_{11}.Which is then congruent to:

*16-2 mod M _{11} ≡ 14 mod M_{11}.*

Therefore, our second residue *s _{1}* is:

*s*

_{1}≡ 14 mod M_{11}.We then use this second residue to calculate our third residue *s _{2}*.

*s*

_{2}≡ s_{2}^{2}-2 mod M_{11}≡ 194 mod M_{11}.We then continue to use this formula to calculate the next six residues:

*s _{3} ≡ 788 mod M_{11.}*

s

_{4}≡ 701 mod M

_{11. }s

_{5}≡ 119 mod M

_{11. }s

_{6}≡ 1877 mod M

_{11. }s

_{7}≡ 240 mod M

_{11. }s

_{8}≡ 282 mod M

_{11}.

We can now finally calculate *s _{9}*, the Lucas-Lehmer residue. This tenth residue turns out to be:

*s*

_{9}≡ 1736 mod M_{11}.Because the Lucas-Lehmer residue must be congruent to *0 mod M _{11}* for

*M*to be a Mersenne prime, the Mersenne number

_{11}*M*is not a Mersenne prime, which matches GIMPS’ own list of the 48 known Mersenne primes.

_{11}= 2047While 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. *M _{48}* is 17.4 million digits long.

Sources:

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

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/