An integer is prime if it is divisible only by 1 and itself. The opposite of prime is composite, because it is the product of primes other than 1. The natural numbers start off thus:
• 1 - "weird prime"
• 2 - prime
• 3 - prime
• 4: { 2, 2 }
• 5 - prime
• 6: { 2, 3}
• 8: { 2, 2, 2 }
• 9: { 3, 3 }
There is no known simple formula to determine if a number of any size is prime. The best we can say is a screen of composites: Aside from 2 and 5, all prime numbers end in one of the digits 1, 3, 7, or 9. Outside of that, the only way to determine if a number is prime or composite is to check it by dividing it by every smaller number.
This can become time-consuming with very large numbers; there is no way at first glance to discover that 4503599627377 is prime, but 4503599627376 has the prime factors of { 2, 2, 2, 2, 3, 37, 1889, 1342409 }.
The difficulty of discovering the nature of a very large integer is inherent to the practice of cryptography. Let's break it down with an example:
Say you have a large file, SECRET.DOC, that you want to keep hidden from prying eyes. We will take that file in binary form (every computer file can be represented as a very big number), and multiply it times a huge prime number. We will also multiply our huge prime times another prime number to get a rare composite number with a difficult set of factors to guess.
Take the example we dropped in the first paragraph: 4503599627370473. It looks like it could be prime, but indeed its prime factors are { 7, 643371375338639 }. We multiply the binary string of SECRET.DOC times the binary representation of 643371375338639.
We can now broadcast SECRET.DOC and the composite number ( 4503599627370473 ) over the public Internet, and SECRET.DOC will be a huge scrambled mess of nonsense data to anyone who does not have the key.
In private, we transmit the number "7" to our intended recipient. They divide the public key ( 4503599627370473 ) by the private key ( 7 ), giving the secret number of 643371375338639 - which, when SECRET.DOC is divided by it, gives back the original file like nothing ever happened.
Note, of course, that we use these numbers only to serve a clear example - these numbers are actually small enough for our calculator to sling around. But you can take the two largest primes we've mentioned here: 643371375338639 and 4503599627377, and multiply them to get a 27-digit number beyond the scope of every publicly available calculator we can find (but not top NSA-quality computing).
It's easy to make a composite number divisible only by two large primes, simply by multiplying two big primes together. But it's very hard to factor that product without knowing one of the factors, hence we have a system where pure math forms a lock and key.
Hopefully, our explanation of prime numbers' importance helped somebody out there understand cryptography for the first time. Prime numbers go on forever, and they are a fascinatingly quirky branch of mathematics, so have fun playing with them!
