How to Find the Next Largest Known Prime

The Electronic Frontier Foundation (EFF) is offering a $150,000 cash prize “to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits” and a $250,000 cash prize “to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits” (https://www.eff.org/awards/coop).  The current largest known prime number, 2^74,207,281 – 1, is just over 22 million digits long and was found on January 7, 2016 by mathematics professor Curtis Cooper using software from GIMPS (the Great International Mersenne Prime Search, http://www.mersenne.org/), an organization where private users can help calculations by donating computer processing time during off-hours via the internet.

A prime number is a number that is only divisible by 1 and itself, and a number that is not prime is called a composite number.  For example, the number 17 is a prime number because it is only divisible by 1 and 17 and no other numbers.  The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, and so on. 

In fact, back in ancient times Euclid proved that the list of prime numbers never ends.  If you suppose that there is a final prime number P, then there exists a number q which equals all the primes multiplied together plus one (q = p₁·p₂·p₃·…·P + 1).  Now, q cannot have a factor because if it did it would divide into q (by definition) and p₁·p₂·p₃·…·P (which has all the primes) and therefore also into 1 (since q = p₁·p₂·p₃·…·P + 1), which is impossible.  So q must be a prime number larger than P, but this contradicts the original assumption that P is the largest prime.  Therefore, there can be no final prime number P, which means the list of prime numbers never ends.  It also means that no matter how big the largest known prime is, there is always a bigger one waiting to be discovered.

There are also no known patterns for the distribution of prime numbers, but there are some tests.  The most basic way to test if a number n is a prime number is to use trial division, which divides the number n by all prime numbers p between 2 and √n.  If any p divides into the number n evenly, then the number n is not a prime number; otherwise if no p divides into the number n evenly, then the number n is a prime number.  For example, if we were to test n = 17 to be prime, we would divide 17 by all the prime numbers between 2 and √17 ≈ 4.1, or by 2 and by 3.  Since neither 2 nor 3 divide evenly into 17, 17 is a prime number. 

Unfortunately, trial division can become cumbersome very quickly with large numbers, because you have to know (and divide by) a list of all the prime numbers between 2 and √n.  Fortunately, there is a more efficient method called the Lucas-Lehmer test which can check whether a number is a Mersenne prime or not (and is also the method used by GIMPS).  A Mersenne prime, named after the French mathematician Marin Mersenne, is a prime number that can be expressed in the form of 2^p – 1.  For example, the number 7 is a Mersenne prime for p = 3, because 2³ – 1 = 7.  The first few Mersenne primes are 3 (p = 2), 7 (p = 3), 31 (p = 5), 127 (p = 7), 8191 (p = 13), and so on.  (It may be tempting to conclude that a Mersenne prime is formed whenever p is a prime number, but this is not true for the prime p = 11, because 2¹¹ – 1 = 2047 = 23·89 which is not prime.  It is true, however, that p must be a prime number for all Mersenne primes.)

The Lucas-Lehmer test uses the recursive sequence s₀ = 4 and s_n = s_n-1² – 2, and states that for all p > 2, s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number.  For example, if we were to test p = 5, where 2^p – 1 = 2⁵ – 1 = 31, we would need to find s_p-2 = s_5-2 = s₃ and see if it is divisible by 31.  So s₀ = 4, s₁ = 4² – 2 = 14, s₂ = 14² – 2 = 194, and s₃ = 194² – 2 = 37634, which is divisible by 31, so 2⁵ – 1 = 31 is a prime number.  Since we are testing divisibility, the algorithm can be made even more efficient by using a modulus function, where s_n = (s_n-1² – 2) mod 2^p – 1, which means the Lucas-Lehmer test can be restated as s_p-2 ≡ 0 (mod 2^p – 1) if and only if 2^p – 1 is a prime number.  So to test p = 5 again, where 2^p – 1 = 31, the sequence would be s₀ = 4, s₁ = (4² – 2) mod 31 = 14, s₂ = (14² – 2) mod 31 = 194 mod 31 = 8, and s₃ = (8² – 2) mod 31 = 62 mod 31 = 0, so 2⁵ – 1 = 31 is a prime number.

Although the Lucas-Lehmer test is difficulty to prove (see here for the proof), it is very easy to program in a computer:

01	# Lucas-Lehmer Mersenne Prime Tester
02	# Python 2.7.3
03	# After running, type "M(p)" where p is the Mersenne Prime exponent in 2^p - 1.
04	#  For example, if you would like to test Mp = 2^7 - 1 = 127, type "M(7)".
05
06	# import python libraries
07	from time import time, strftime
08	import datetime
09
10	# M function
11	def M(p):
12	# make sure p > 2, a restriction for the Lucas-Lehmer algorithm
13	if p > 2:
14	# start timer
15	timestart = time()
16	# find Mp
17	Mp = 2 ** p - 1
18	# Lucas-Lehmer algorithm
19	s = 4
20	for x in range(0, p - 2):
21	s = (s * s - 2) % Mp
22	# display results
23	if s == 0:
24	print "2^" + str(p) + " - 1 is PRIME"
25	else:
26	print "2^" + str(p) + " - 1 is COMPOSITE"
27	#display elapsed time
28	timeelapsedint = round(time() - timestart, 2)
29	timeelapsedstr = str(datetime.timedelta(seconds = round(
30	timeelapsedint, 0)))
31	print "runtime: " + timeelapsedstr + " or " + str(
32	timeelapsedint) + " seconds."
33	else:
34	# p <= 2, so display a message to ask for p > 2
35	print "Please enter a number larger than 2."

Here’s what happens when you use this program to test a somewhat large Mersenne prime, 2^11,213 – 1, which has approximately 3,000 digits, on a dual-core 1.67 GHz processor (a mediocre-speed laptop for 2016):

>> M(11213) 2^11213 - 1 is PRIME runtime: 0:00:55 or 54.64 seconds.

So with less than 40 lines of code, you can use your computer to verify that a 3,000 digit number is prime in less than one minute!

Not bad, but this is still a far cry from the current record of 22 million digits, and an even further cry from the future cash-prize-awarding prime of 100 million digits.  In any case, finding the next largest prime number will require an educated guess, a fast computer (or more), and lots and lots of patience.