Basics of Cryptography, Part 1 / 12

Imagine we are living in prehistoric times. Now, consider the following. How did we keep track of time without a clock? All clocks are based on some repetitive pattern which divides the flow of time into equal segments. To find these repetitive patterns, we look towards the heavens.

The sun rising and falling each day is the most obvious. However, to keep track of longer periods of time, we looked for longer cycles. For this we looked to the moon, which seemed to gradually grow and shrink over many days. When we count the number of days between full moons, we arrive at the number 29.

This is the origin of a month. However, if we try to divide 29 into equal pieces, we run into a problem. It is impossible. The only way to divide 29 into equal pieces is to break it back down into single units. 29 is a prime number. Think of it as unbreakable.

If a number can be broken down into equal pieces greater than one, we call it a composite number. Now, if we are curious, we may wonder how many prime numbers are there, and how big do they get? Let’s start by dividing all numbers into two categories. We list the primes on the left, and the composites on the right.

At first they seem to dance back and forth. There is no obvious pattern here. So let’s use a modern technique to see the big picture. The trick is to use a Ulam spiral. First we list all possible numbers in order in a growing spiral. Then we color all the prime numbers blue. Finally, we zoom out to see millions of numbers. This is the pattern of primes, which goes on and on forever.

Incredibly, the entire structure of this pattern is still unsolved today. We are on to something. So let’s fast forward to around 300 BC in ancient Greece. A philosopher known as Euclid of Alexandria understood that all numbers could be split into these two distinct categories. He began by realizing that any number can be divided down over and over until you reach a group of smallest equal numbers.

And by definition, these smallest numbers are always prime numbers. So he knew that all numbers are somehow built out of smaller primes. To be clear, imagine the universe of all numbers, and ignore the primes. Now, pick any composite number and break it down, and you are always left with prime numbers. So Euclid knew that every number could be expressed using a group of smaller primes.

Think of these as building blocks. No matter what number you choose, it can always be built with an addition of smaller primes. This is the root of his discovery, known as the fundamental theorem of arithmetic, as follows. Take any number, say 30, and find all the prime numbers it divides into equally. This we know as factorization. This will give us the prime factors.

In this case, 2, 3, and 5 are the prime factors of 30. Euclid realized that you could then multiply these prime factors a specific number of times to build the original number. In this case, you simply multiply each factor once to build 30. 2 times 3 times 5 is the prime factorization of 30.

Think of it as a special key, or combination. There is no other way to build 30 using some other groups of prime numbers multiplied together. So every possible number has one, and only one prime factorization. A good analogy is to imagine each number as a different lock. The unique key for each lock would be its prime factorization. No two locks share a key. No two numbers share a prime factorization.