The Time Of Primes

I read a while ago that somebody had found a new prime number. I didn't think too much of it at first, apart from the question of why would anybody still be doing this.

Apparently I'm not the only person. When the story first came up, a friend at work asked me (probably because I have a degree in Math and he thought I'd know this kind of thing) if this new prime number was going to be able to do anything special. After some googling and admissions of how uninformed I was, I told him that primes can be useful for cryptography, but only smaller primes (100-200 digits).

Apart from that, I just wondered how easily I could create a program to calculate primes. Well, the answer was pretty easily. See for yourself -

while (true)
{
  if (numberIsPrime(number))
  {
    Console.WriteLine(number.ToString());
  }
  number += 1;
}

private static bool numberIsPrime(int number)
{
  // Loop through all the numbers from 1 - number
  for (int numberCount = 1; numberCount <= number; numberCount++)
  {
    // If the modulus of the number is 0, it means it divided without a remainder
    if (number % numberCount == 0)
    {
      // The number can divide itself and 1 and still be a prime
      if (numberCount != 1 && numberCount != number) return false;
    }
  }
  // If we got this far, return true, it's a prime
  return true;
}

So that was it for a while. I didn't think about it for 6 months or so.

Then for some reason it popped back into my mind. I think when I read the story about the new prime I did check the number, but it obviously didn't register with me. This time I went back to the story and thought about the actual prime number. Well, in case you're interested, the number is 2^57,885,161− 1. That actually works out at being a number with 17 million digits (17,425,170 to be exact, and why shouldn't we be when we're working with primes).

It's hard to visualize a number that long with any real clarity, so I'm going to try and give you something to compare it to. I thought back to my Physics days and some of the huge numbers we dealt with. The number of atoms in the universe (the whole universe) is estimated to be a number of only 80 digits. OK, not even close, let's go bigger, something stupid like star distances. Well the "width" of the universe is a number with only approximately 30 digits.

Clearly nothing else is on the scale of prime number calculations.

OK, so even if we ignore the very scale of the number, I was intrigued as to how long it might take to calculate a number like that using a regular computer. Now regular here, is in regards to super computers. I have an Intel Core i7, with 8Gb of RAM, so my laptop is top of the line.

Currently, all the latest top prime numbers are being discovered by a distributed internet project known as the Great Internet Mersenne Project. Here's a list of the numbers they've found -

Now this is not an official record of time spent, but according to this list it took them close to 4 years to find this latest prime number. At first glance, that seems crazy, but after spending a little time finding primes I'm not so sure.

Yes, the final step of this investigation (can you call one guy messing around an investigation?) is me finding out how long it would take one person to find this prime number. Obviously, I'm not using parallel processing, so in theory it's going to take more than 4 years, and I don't want to wait over 4 years to blog about these results, so I used a little math and some good old excel graphs to get a rough idea.

First, I modified my program above to log the time taken to find each prime number, and then let it go for an afternoon. The largest prime I calculated was 5590853 (only 7 digits) and on the way I found 3866 other primes. It took me 3 hours and 13 minutes to find this prime.

Using this data I calculated a best line graph with the following equation -

y = 9.385552520679E-08e1.133509190066E+00x

Comparing this equation to the actual results was only an error of 12.5%. Admittedly, not great, but good enough for our purposes. I then tried to use this equation to calculate how long it would take to find the largest prime number, but excel couldn't handle it. The largest it could get to was 2^600 (keep in mind the largest prime is 2^57,000,000). It would take 2.6*10¹²⁵ seconds. That's a number with 125 digits in it, already bigger than the number of atoms in the universe. That's more time than the age of the universe. A lot more time.

Once I realized this, there really was nowhere else to go with it. Obviously, a single person calculating prime numbers is now completely ridiculous.

I hate to go out on a low, but this was really the end of my investigation. It turns our when you get to this scale, everything is too big to comprehend. Every number is hypothetical, as nothing exists in the universe in a quantity that even gets close to these primes.

At the start of this post, I talked about why would anybody even bother calculating primes anymore, but then I spent hours of my time calculating how long it would take to calculate the primes. I'm worse than they are, but yet in doing all this, I kind of discovered why people are probably still doing this. It's pure human interest. What does it take to find the next one, and how long will it take? The last one took 4, but could the next one take 20? Who knows, but I think now at least I understand why they're doing it.