What are prime numbers
What are prime numbers, and why are they so vital to modern life?
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.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.
This allows us to get around the core paradox of encryption: How do you securely communicate the initial specifics needed to set up secure communication in the first place? In public key cryptography, which is the backbone of computer encryption, we can get around this because the specifics of how to get into secure contact don’t themselves need to be secure. Quite the opposite — people generally post links to their public keys on social media, so as many people as possible will be able to encrypt messages for them. Though there are now quite a few encryption algorithms that exploit prime factorization, the most historically significant, and still the conceptual blueprint for the field, is called RSA.
Whether it’s communicating your credit card
information to Amazon, logging into your bank, or sending a manually encrypted email to a colleague, we are constantly using computer encryption. And that means we are constantly using prime numbers, and relying on their odd numerical properties for protection of the cyber-age way of life. It’s no meaningless academic quest, the effort to better understand prime numbers, since virtually all of modern security relies upon the current limitations of that understanding.That’s all not to say that there has been no progress in factoring large numbers. In 2009, researchers networked several hundred computers together and spent the equivalent of about 2,000 years for a single computer, using advanced factoring algorithms to factor the “RSA-768″ number — that is to say, a number with 232 digits put up by the RSA group as a factoring challenge. Proving it was possible to break 768-bit encryption in non-universal-heat-death timescales is unacceptable for the security world, of course, and so the standard has now moved to RSA-1024, using numbers with 309 digits.
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. As Carl Sagan points out so eloquently in the novel Contact, 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