Sequentia Explores: The Mathematics of Crypto
Part II: The Mathematician’s Toolkit
Lecture 13: Fermat’s Little Theorem: A Simple-Looking Rule with Profound Power
In our journey through the mathematician’s toolkit, we’ve encountered modular arithmetic, primes, and the powerful operation of modular exponentiation. Today, we’ll look at a theorem that elegantly ties all of these concepts together. It comes from the brilliant 17th-century mathematician Pierre de Fermat, a lawyer who practiced mathematics as a hobby but ended up producing some of the most profound results in number theory.
We’re talking about Fermat’s Little Theorem. Don’t be fooled by the “Little” in its name—it’s only called that to distinguish it from his more famous “Fermat’s Last Theorem.” This theorem is a giant in the world of cryptography.
The Theorem Stated Simply
Fermat’s Little Theorem describes a fascinating property that occurs when you raise a number to a power mod p, where p is a prime number.
The theorem states:
If p is a prime number, then for any integer a that is not a multiple of p, it is true that:
a^(p-1) ≡ 1 (mod p)
Let’s break that down with an example.
- Let’s pick a prime number, p = 7.
- Let’s pick an integer a that is not a multiple of 7, say, a = 2.
- The theorem predicts that 2^(7-1) should be congruent to 1 (mod 7). Let’s check it.
- We need to calculate 2^6 mod 7.
- 2^6 = 64
- Now, we divide 64 by 7. 64 = 9 × 7 + 1.
- The remainder is 1.
- The theorem holds true! 2^6 ≡ 1 (mod 7).
Let’s try again with p = 5 and a = 3.
- The theorem predicts 3^(5-1) ≡ 1 (mod 5).
- We need to calculate 3^4 mod 5.
- 3^4 = 81
- 81 = 16 × 5 + 1.
- The remainder is 1.
- It works again! 3^4 ≡ 1 (mod 5).
This isn’t a coincidence. This relationship holds true for any prime p and any integer a not divisible by p. It reveals a deep, underlying structure in the world of modular arithmetic.
An alternative form of the theorem, which is true for any integer a (including multiples of p), is:
a^p ≡ a (mod p)
You can see that if you divide both sides by a, you get back to the original form.
Why is This So Important? Two Major Applications
This simple-looking rule is not just a mathematical party trick. It is a workhorse with two critical applications in cryptography.
Application 1: Primality Testing
Remember how important large prime numbers are for public-key cryptography? How do we find them? How do we check if a massive, 300-digit number is actually prime?
Dividing it by every number up to its square root would take an impossibly long time. This is where Fermat’s Little Theorem comes to our aid.
If we have a large number n and we want to test if it’s prime, we can pick a random number a (less than n) and calculate a^(n-1) mod n.
- If the result is NOT 1, then we know with 100% certainty that n is not a prime number (because if it were prime, the result would have to be 1, according to the theorem). n has failed the test and is composite.
- If the result IS 1, then n is probably a prime number.
This is called the Fermat primality test. It’s a probabilistic test. While a result of 1 doesn’t give 100% proof (due to a rare class of composite numbers called Carmichael numbers that can fool the test), the chances of a composite number passing the test for many different random choices of a are astronomically small. By repeating the test with several different random a’s, we can achieve a level of certainty that is high enough for all practical cryptographic purposes.
This test provides a fast and efficient way to sift through countless large numbers and find the probable primes we need to build our cryptographic keys.
Application 2: A Cornerstone of the RSA Algorithm
Fermat’s Little Theorem is a key ingredient in proving that the RSA encryption algorithm actually works. RSA is one of the most widely used public-key cryptosystems in the world, and its decryption process relies on this theorem.
We won’t go through the full RSA proof here (that’s for a future lecture!), but here’s the essence of the connection:
In RSA, a message M is encrypted by calculating C = M^e mod n.
To decrypt it, the receiver calculates C^d mod n, which turns out to be (M^e)^d mod n.
The clever mathematics used to choose the encryption exponent e and the decryption exponent d are designed specifically to leverage a more general version of Fermat’s Little Theorem (called Euler’s Totient Theorem). This ensures that M^(e×d) simplifies in a way that, after the modulo operation, you get back to your original message M.
In other words, Fermat’s Little Theorem is the mathematical guarantee that when you encrypt a message with an RSA public key and then decrypt it with the corresponding private key, you get your original message back, perfectly intact. It’s the reason decryption is not just a random guess, but a predictable mathematical outcome.
Fermat’s Little Theorem is a bridge. It connects primes and modular exponentiation, providing us with both a practical tool for finding our cryptographic building blocks and the theoretical foundation for one of the most important encryption algorithms ever devised.
In our next lecture, we’ll explore the more general version of this theorem, Euler’s Totient Theorem, which extends these powerful ideas beyond just prime moduli.
