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.

Over the last few days, the internet news has been filled with stories of an Iraq-born 16-year-old boy who “cracked the mystery of the Bernoulli numbers”. This has of course been promptly been picked up by dozens of blogs and regurgitated all over the place. However, if you’re mathematically-inclined like me, this might lead you to wonder “there was a mystery of the Bernoulli numbers?” Well, wonder no more, because no there was not. The formula for B_n, the n^th Bernoulli number, that was “discovered” by the boy is as follows:

This formula was originally derived by a mathematician named Julius Worpitzky in 1883. Some sources have tried half-heartedly to correct the article by appending a sentence to the bottom of the story:

Later, a clarification was given‚ by the mathematical community that the probable solution to this century old problem was available in mathematical circuits though not openly available to all.

– thaindian.com

The problem is that this isn’t even true; the “probable solution” (what does that mean, exactly?) was not under some mysterious mathematical lock-and-key. It was well-known and even included on the Wikipedia page describing the Bernoulli numbers (at the time of this writing, it is about halfway down the page under the section titled “Connection with the Worpitzky number”). Uppsala University has even issued an official statement saying that the news articles are false.

So while the boy’s derivation of the formula is indeed impressive considering his age (if he did indeed derive it himself rather than following the steps outlined on the wiki page), the story about this “puzzle” being solved is almost entirely false.

Update [June 6, 2009]: The Mathematical Association of America has now posted an article about this same topic.

Up’s balloon house

Let me say right off the bat that I am in no way insulting or belittling the new Pixar film Up, which was released in theatres this weekend; it was one of Pixar’s better outings, and that’s saying something. However, after reading a ridiculous article on PopularMechanics.com that actually defends the physical plausibility of Up, I couldn’t help but write a thing or two about the (im)plausibility of the movie myself.

The absurdness of the article appears as early as its fourth sentence:

Given the fact that one cubic foot of Helium can lift 60 pounds, with even small, 1 x 1-foot balloons, Carl’s rig has the capacity to lift about 618 tons—enough to lift about 150 Hummers.

– PopularMechanics.com

Let’s think for a second about the numbers in that sentence, shall we? One cubic foot of helium can lift 60 pounds. Really, PopularMechanics? When was the last time that you were at a fair and saw a full-grown man get carried away by four helium balloons? How about instead of putting window washers and construction workers on scaffolding, we just tie a handful of balloons to their waist? Seems like a more economical solution to me.

Indeed, since PopularMechanics.com can’t seem to be bothered, let’s do some actual math to figure out how plausible the situation in Up really is. Helium’s density is about 5.06 grams per cubic foot and the density of air is roughly 36.11 grams per cubic foot. Thus, one cubic foot of helium can lift roughly 31.05 grams (this number will vary slightly depending on what figure you use for air density and whether or not you include the weight of the balloon itself, but I think that we can all agree that it is slightly less than 60 pounds).

Assuming that the average balloon indeed holds a cubic foot of helium (this seems like a reasonable assumption to me), we then find that it would take some 2630 balloons just to lift a 180-pound old man. To pick up his house (assuming a weight of 50 tons, which seems reasonable to me) as well would then require some 1.46 million balloons—a far cry from the reported 20622 balloons that were actually used. But hey, 20622 balloons would be enough to lift about 1400 pounds, or just under 3/4 of a ton. That’s pretty close to what you said, right PopularMechanics?

Update [June 1, 2009]: PopularMechanics has now corrected their article by replacing the offending text with “Given the fact that Helium can lift over six times its weight, Carl’s idea isn’t entirely fiction.”