Background

Prime numbers are pretty important to mathematics. They form the basis of many problems in number theory, and they are the building blocks of multiplication, as all numbers can be made by multiplying a unique set of primes together.

And yet, for something so simple, the primes are legendarily hard to pin down. They appear unpredictably on the number line, even while they’re fixed in place. It’s hard to tell if a given number is prime or not, or what the prime factors of a given number are.

Due to this computational difficulty, it’s become a common task in computing to try and find larger and larger primes. The current largest known prime number has over 22 million digits. Technically, as there are infinite primes, there is no “largest” prime, but there is certainly a largest found prime.

So, how exactly do you find a large prime? There are two necessary elements to this – fast computers (or more likely, distributed computing), and a good method for finding the primes. The most basic method for finding primes is to try dividing it by 2, by 3, by 5, and keep dividing by all the primes up to the square root of the number, and see if any of them divide neatly. If they don’t, it’s prime.

For finding large primes, this is incredibly impractical, so they’ve found faster algorithms. This is a quick explanation of the most common one, the Lucas-Lehmer test.

Mersenne Primes

This test is very quick at determining whether a number is prime or not, but there is a catch – it only works on certain kinds of numbers. All of the largest primes that have been found are a form of number called a Mersenne number, which is any number 1 less than a power of 2:

Mn = 2n-1

This is because the Lucas-Lehmer test only works to determine if Mersenne numbers are prime. So, why would we use such a limited test? Because it’s faster than any other that has been devised. To be fair, when you have large values of n, it still takes considerable computer time, but it might take a few weeks, where dividing by all smaller numbers might take, on the same computer, the lifetime of the universe. So, how does it work?

Lucas-Lehmer test

This is how the test works. Say you want to know if, for example,

27-1

is prime or not. First of all, you need to make a number sequence, where the first term, T1 is 4, and each successive term is the previous term squared, take away 2.

T1 = 4
T2 = 42-2 = 14
T3 = 142-2 = 194
Tn = (Tn-1)2-2

Then, you take our exponent (in this case, 7), and take away 1, to get 6. Take this sequence we just defined, and go to the 6th term, which in this case is

T6 = 2005956546822746114

And we divide it by our whole number, which is 27-1. Now, the question is – do we get a remainder after this division? In this case, no we get 15794933439549182, a nice integer. this means that the number is prime.

In case it didn’t quite make sense, here is a summary of the process:

  1. Take your number, 2n-1, and this odd sequence we defined.
  2. Go to the (n-1)th term on the list, and see if it has a remainder when divided by 2n-1.
  3. If it doesn’t, then it is prime – if it does, it’s a composite number.

You may notice that there is still a flaw in this process – the numbers get very large, very quickly. while the first few terms of the sequence are quite small, by the time you get to term 10, it’s a 293 digit number. As it turns out, happily, there is a simple way to fix this.

Improving the process

First of all, it helps to define something called the mod function. Essentially, the mod function finds the remainder after dividing one number by another. It looks like this:

M%N = Remainder after dividing M by N

For example,

7%2 = 1

When  we go to the (n-1)th term of the list and divide by our candidate for prime, we only really care about the remainder. This means that, whenever a term on the list gets above our number 2n-1, we take the remainder mod 2n-1, and use that instead as the next number in the sequence. For example, if our number is 25-1 (31), then we get:

4%31=4

42-2=14, 14%31=14

142-2 = 194, 194%31=8

82-2 = 62, 62%31=0

And as 0 is our fourth term (n-1), we don’t even need to divide by our number and look for the remainder, as our result is already the remainder. This process means the numbers never get any larger than our candidate prime. They can still get very large, but it is certainly an improvement.

For funsies, here’s a python implementation of this process.

#Run LL(n), where n is the exponent of the Mersenne number, to see if it's prime
def LL(n):
    PotPrime = 2**n-1
    a = 4
    Seq = [4]
    for x in range(2,n):
        a = (a**2-2)%PotPrime
        Seq.append(a)
    return Seq[n-2] == 0

For example, running LL(89) tells you that 289-1 is prime.

If you find a nice large number, and you want to see how many digits it is, take the exponent (in this case, 89), and multiply it by 3/10 and add 1, then round down to the nearest whole number. This will (roughly) give you the number of digits (so (289-1) is 27 digits long.) For a precise formula, use:

Digits(2n-1)=⌊nlog102⌋+1

Where those ⌊⌋ symbols simply mean round down whatever is between them (so, 2.4 becomes 2, and 2.9 also becomes 2 – always round down.) I’ll admit, I know this doesn’t take the (-1) into account, but it’s unlikely to cause problems.

The largest number that I’ve found to be prime is 29941-1, which is a few short of 3000 digits long.

UPDATE now the program has spat out 219937-1 as prime. All these primes have already been found, but it’s still cool to look for them.

Great Internet Mersenne Prime Search

If you want to take part in the search for these large Mersenne primes, look up the Great Internet Mersenne Prime Search, and download their software, which is much more optimised and clever, and will let you factor larger numbers. Who knows? Maybe you’ll find the next largest one!

How do we know the Lucas-Lehmer test works?

Good question! There’s a nicely written explanation of the proof here (note that it goes on for some 30 blog posts, it’s not a short explanation.) Note that this doesn’t prove that if a Mersenne number is prime, it passes the test – it only proves that if a Mersenne number passes the test, then it must be prime.

Advertisements