Here’s something cool about primes: Mathematicians have shown that absolutely any whole number can be expressed as a product of primes, only primes, and nothing else.

For example:

    To get 222, try 2 * 3 * 37

    123,228,940? Why, that’s just, 2 * 2 * 5 * 23 * 79 * 3391

This rule, called the prime factorization rule, is called something else as well: the Fundamental Theorem of Arithmetic. It makes sense when we think about what primes are, numbers that can’t be pulled apart any further. So as we try to pull apart any number into two numbers, then pull those apart into two numbers if possible, and so on, we will eventually be left only with primes.

This all might seem like nothing more than a cool mathematical oddity. But it becomes important thanks to one simple additional fact: As far as the best mathematicians and computer scientists have been able to determine, it is totally impossible to come up with a truly efficient formula for factoring large numbers into primes.

This all might seem like nothing more than a cool mathematical oddity. But it becomes important thanks to one simple additional fact: As far as the best mathematicians and computer scientists have been able to determine, it is totally impossible to come up with a truly efficient formula for factoring large numbers into primes.

That is to say, we have ways of factoring large numbers into primes, but if we try to do it with a 200-digit number, or a 500-digit number, using the same algorithms we would use to factor a 7-digit number, the world’s most advanced supercomputers still take absurd amounts of time to finish. Like, timescales longer than the formation of the planet and, for extremely large numbers, longer than the age of the universe itself.

So, there is a functional limit to the size of the numbers we can factor into primes, and this fact is absolutely essential to modern computer security. Pretty much anything that computers can easily do without being able to easily undo will be of interest to computer security. Modern encryption algorithms exploit the fact that we can easily take two large primes and multiply them together to get a new, super-large number, but that no computer yet created can take that super-large number and quickly figure out which two primes went into making it.

This math-level security allows what’s called public key cryptography, or encryption where we don’t have to worry about publishing a key to use in encrypting transmissions, because simply having that key (a very large number) won’t help anyone to undo the encryption it created. In order to undo the encryption, and read the message, you need the prime factors of the key used for encryption — and as we’ve been seeing, that’s not something you can just figure out on your own.


1024-bit encryption ought to still be safe from anyone not in possession of a time machine, so far as we know — though rumors abound on the internet of secret quantum computer projects at the NSA or elsewhere, ones that can chew through even 2048-bit encryption like it ain’t nothing. There’s absolutely no evidence that such a thing exists, however.

Prime numbers are cool. There’s a certain importance to their status as the most fundamental building block of all numbers, which are themselves the building blocks of our understanding of the universe. In that book, aliens choose to send a long string of prime numbers as proof that their message is intelligent and not natural in origin, since primes are one thing that cannot change due to differences of psychology, lifestyle, or evolutionary history. No matter what an advanced alien life-form looks or thinks like, if it understands the world around it, it almost certainly has the concept of a prime.

That’s why a lot of mathematicians view number theory as a little bit like archaeology. The feeling isn’t one of inventing new technologies, but of uncovering the logical foundations of the universe, those that describe its behavior everywhere, throughout all of time.