Blog > No, Primes with Millions of Digits Are Not Useful for Cryptography

No, Primes with Millions of Digits Are Not Useful for Cryptography

September 11th, 2009

About once a year, the internet news fills up for a week or so with talk of how a new largest-known prime has just been found. This largest-known prime has invariably been found by GIMPS, a distributed computing project designed to find large Mersenne primes.  Of course, mainstream media doesn’t like reporting things unless they can give people the illusion of some sort of immediate practical purpose. So what to do when you can’t think of a practical use for some recently-discovered 10-million-digit prime numbers? Make one up, of course! Just say that they have applications in cryptography:

Scientists in the US and Germany have found the two largest prime numbers ever calculated in a discovery which could dramatically increase the effectiveness of cryptographic systems.

- v3.co.uk

The Source of the Myth: RSA Encryption

Like all good myths, the Mersenne prime cryptography myth is so widespread because it is so close to being true. The most widely-used form of encryption used on the internet is RSA encryption, which works by multiplying two huge prime numbers together to form an even larger number with exactly two prime factors. Since factoring numbers is believed to be computationally difficult, reversing this process is currently a very difficult problem, which leads to RSA providing reasonably strong encryption. The thing is, RSA typically uses primes that have a few hundred digits, not a few million digits. Some of the reasons for this are as follows:

  1. You don’t need to use million-digit primes. Considering that even cracking RSA that uses 250-digit primes is an extremely difficult problem that hasn’t been completed yet, and the problem gets exponentially more difficult as you add more digits, even the most paranoid of people should be comfortable using primes with a couple thousand digits. You might argue that some big government agencies would want RSA to be as secure as possible for their transactions, so they might want to use million-digit primes, but any agency that is that worried about security shouldn’t be using public key cryptography in the first place.
  2. Using primes with millions of digits actually decreases security. As of this writing, there are 26 known primes with more than one million digits, so to break RSA encryption that makes use of primes with millions of digits you can just test each one of the known million-digit primes to see if they are one of the factors. RSA only works because there are lots of primes with hundreds of digits to choose from (as in billions of billions of billions of them, and then some).
  3. Manipulating numbers with millions of digits is slow. Internet-based public key cryptography systems need to be fast if they’re to be of any practical use, so it doesn’t make much sense to try to use a cryptography system that relies on multiplying and finding residues with numbers that take several megabytes just to store. Just imagine trying to do some online banking when you have to transmit this number along with every other piece of data that you send back to the server.

Not all media outlets are so bad as to directly say that the primes found by GIMPS are useful for cryptography, but the vast majority of them imply it at some point throughout the story. Consider the following examples, which are taken from stories about newly-discovered GIMPS primes:

Mersenne primes are important for the theory of numbers and they may help in developing unbreakable codes and message encryptions.

- BBC News

Current cryptographic systems rely on the challenge of factoring large primes.

ScienceNews.org

While those tidbits of information are quite true (well, almost — see the comments), when taken in context they are entirely misleading and cause the reader to think that GIMPS primes have applications in today’s cryptography systems. It’s like running a story about a recent plane crash that includes a sentence about how it’s a good idea to wear a helmet when riding a bicycle.

So Why Do We Search for Huge Primes?

The main reason that we search for huge primes is simply for sport. It gives our idle CPU cycles something to do. Non-mathematicians seem to balk at that idea and call it a huge waste of CPU cycles/time, and they’re probably right, but so what? Have you ever played a video game? This is our version of going for a high score. If that doesn’t seem like a particularly good reason to you, perhaps one of the reasons given by GIMPS itself will satisfy you. One thing that you’ll notice though is that cryptography is not mentioned anywhere on that page.

  1. September 11th, 2009 at 10:47 | #1

    I assume ScienceNews.org means: “Cryptographic systems rely on the challenge of factoring numbers which are the product of two large primes.” This is something else that the media almost always messes up, but give the overall level of math illiteracy in media, I suppose it’s not that surprising.

  2. September 11th, 2009 at 11:01 | #2

    @Nathan – Yeah, it’s pretty embarrassing for such a mistake to be made on ScienceNews of all places. Such a mistake I could potentially see just being someone’s mind going to sleep while typing that sentence (as opposed to flat-out making stuff up like some other sources), but it’s a little sad that it made it past whatever editor they have there.

  3. Jose
    April 19th, 2013 at 20:38 | #3

    Thanks for debunking this myth. I had a math professor at my university spreading this misinformation.

  4. July 27th, 2014 at 08:47 | #4

    before tanning formula is applied because they act as barriers to your
    tan. You would no longer need to deal with harmful ultraviolet radiation from sunlight thereby, reducing the chances
    of wrinkles, dark spots, sunburns, premature ageing
    and skin cancer. It may set a trend away from the sun and tanning beds whose dangers have prompted warnings from the Food
    and Drug Administration and the World Health Organization. ” It’s estimated that in USA incomparable upwards of 20 million grouping experience from the unhealthiness, with varied degrees of affliction, hurt and unhappy accompanying the malady. Spray tanning has become a new version of safe tanning. If you want to do this than apply an extra layer of the self tanner to all of the unaffected parts of you skin to “fill
    in” the tan. To get rid of this problem, a number of alternative methods have hit the market in London over the last decade.
    For Valentine’s Day, Mobile Tan LA is giving a 10% discount on all airbrush tan’s including a full body spray tan. Sunless tanning came
    into the picture when the harmful effects of ultraviolet rays of the sun were discovered and people started fearing overexposure
    to it. The ASYANA self tanning products & tanning lotion are not only helpful products for
    the tanning key but also take place to be amongst the reasonably priced ones.

  5. July 27th, 2014 at 21:28 | #5

    Sitting below the bladder and in front of the rectum, the prostate gland is wrapped around the urethra and is responsible
    for the production of the clear liquid that makes up 30% of the seminal
    fluid. Organic farmers must follow specific guidelines to become certified.
    This is an embarrassing condition, is due to weakened
    pelvic floor muscles, and which can be rectified by strengthening these muscles
    using pelvic floor exercises or Kegel exercises.

  1. No trackbacks yet.