Sequentia Explores: The Mathematics of Crypto
Part II: The Mathematician’s Toolkit
Lecture 7: Prime Numbers: The Indivisible Atoms of Cryptography
In our last lecture, we explored the cyclical, predictable world of modular arithmetic. We now have a powerful tool for working with numbers in a finite space. Today, we add the second cornerstone of our mathematical toolkit: a special class of numbers that are, in many ways, the polar opposite of clocks. They are not cyclical; they are fundamental, indivisible, and beautifully stubborn.
We’re talking about prime numbers.
You likely encountered primes in school: a prime number is a whole number greater than 1 that cannot be formed by multiplying two smaller whole numbers. In other words, its only divisors are 1 and itself.
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23…
While this definition seems simple, these numbers possess unique properties that make them the “indivisible atoms” of number theory and, consequently, indispensable for modern cryptography.
The Fundamental Theorem of Arithmetic: Primes as Building Blocks
One of the most elegant truths in all of mathematics is the Fundamental Theorem of Arithmetic. It states that every integer greater than 1 is either a prime number itself or can be represented as a unique product of prime numbers.
Think of it like this:
- Composite numbers (non-primes) are like molecules.
- Prime numbers are the atoms that form those molecules.
Let’s take the number 60.
60 = 2 × 30
30 = 2 × 15
15 = 3 × 5
So, the unique prime factorization of 60 is 2 × 2 × 3 × 5 (or 2^2 × 3 × 5). No matter how you start breaking down 60, you will always end up with this exact set of prime “atoms.” This unique factorization is a mathematical certainty.
This property alone is powerful, but it’s the difficulty associated with it that truly excites cryptographers.
The Asymmetric Trapdoor: Easy to Multiply, Hard to Factor
Herein lies the central secret that underpins much of modern public-key cryptography. Consider this simple puzzle:
Easy Task: What is the product of 17 and 23?
You can likely do this with a pen and paper, or certainly a calculator, in seconds.
17 × 23 = 391
Hard Task: What are the two prime numbers that multiply together to give 391?
This is much harder. You might have to start testing primes: Is it divisible by 3? No. By 5? No. By 7? No… and so on. Eventually, you would find that 391 = 17 × 23. The process of finding these original prime factors is called integer factorization.
While this was just a small example, this asymmetry in difficulty scales dramatically.
- Multiplication (Easy):Â A computer can multiply two 300-digit prime numbers together in a fraction of a millisecond. The result would be an enormous 600-digit number.
- Factorization (Impossibly Hard): If you give that same 600-digit number to the most powerful supercomputers on Earth, and you tell them it’s the product of two large primes, it could take them trillions of years to find the original two prime factors.
This is not a matter of having a slow computer; it’s a matter of computational feasibility. There is simply no known “shortcut” (classical algorithm) to quickly factor large numbers. You essentially have to resort to brute-force guessing in a very, very large haystack.
This creates what cryptographers call a trapdoor function: a function that is easy to compute in one direction (multiplying the primes) but incredibly difficult to reverse (factoring the product) unless you have a special piece of secret information—in this case, one of the original prime factors.
How Primes Create Security
This “easy-to-do, hard-to-undo” property of prime factorization is the magic ingredient for public-key cryptography, which we will explore in detail later.
Imagine Alice wants to create a secure lock. She secretly chooses two massive prime numbers, p and q. She multiplies them together to get a huge number, N = p × q.
- She can publicly announce N to the entire world. This number N is part of her public key. Anyone can use it to encrypt a message to send to her.
- The original prime factors, p and q, she keeps absolutely secret. These primes are part of her private key.
An eavesdropper, Eve, sees the public number N. To break the encryption, she would need to figure out the secret primes p and q. But as we’ve discussed, factoring the enormous number N is computationally infeasible.
Alice, however, knows the secret trapdoor information (p and q). She can use her private key to quickly and easily decrypt any messages that were encrypted using her public key N.
The security of this entire system rests on the simple, proven fact that factoring large numbers is extraordinarily difficult.
The Never-Ending Hunt for Primes
The search for ever-larger prime numbers is a serious endeavor for mathematicians and computer scientists. Distributed computing projects like the Great Internet Mersenne Prime Search (GIMPS) harness the power of thousands of computers to find new, record-breaking primes.
Why? Because the larger the primes we use in cryptography, the larger and harder-to-factor the resulting public numbers become, making our encryption systems more secure against the ever-increasing power of computers.
Prime numbers are not just a mathematical curiosity. They are the quiet, indivisible, and unyieldingly difficult guardians of our digital secrets. Their stubborn refusal to be easily factored is one of the main reasons you can securely shop, bank, and communicate online.
In our next lecture, we’ll return to our first cipher, The Caesar Cipher, and put our knowledge of modular arithmetic into practice.
