Mathematics
Euler's Totient Function and Its Cryptographic Applications
Quick fact
Euler's totient function φ(n) not only counts the integers from 1 to n that share no prime factors with n, but its value for a product of two distinct primes p and q is simply (p−1)(q−1), and this exact value is what makes RSA encryption work.
Why this is interesting
You probably know that your credit card number is encrypted when you buy something online. But did you know that the security of that encryption relies on a simple counting function invented by Leonhard Euler in the 18th century?
Read the full explanation
Understanding Euler's Totient Function and Its Cryptographic Applications
Imagine you have a set of numbers from 1 to n. Euler's totient function, written φ(n), counts how many of those numbers are 'coprime' to n—meaning they have no common divisor with n other than 1. For example, φ(10) = 4 because the numbers 1, 3, 7, 9 are coprime to 10, while 2, 4, 5, 6, 8 are not. This count might seem abstract, but it has a surprising property: if n is a product of two distinct primes p and q, then φ(n) = (p−1)(q−1). This formula is the key that unlocks RSA encryption. In RSA, you pick two large primes, compute their product n, and then φ(n) is used to generate the public and private keys. The security relies on the fact that it's easy to compute φ(n) if you know the prime factors, but extremely hard if you only know n.
A deeper explanation
The deeper reason φ(n) is so important in cryptography is Euler's theorem: if a is coprime to n, then a^φ(n) ≡ 1 (mod n). This means that if you raise a number to the power φ(n), you get back to 1 modulo n. In RSA, the encryption exponent e is chosen to be coprime to φ(n), and the decryption exponent d is the multiplicative inverse of e modulo φ(n). Because of Euler's theorem, raising a message to the power e and then to the power d gives back the original message. The security lies in the fact that finding φ(n) without knowing the prime factors is as hard as factoring n itself. Thus, the totient function is not just a counting curiosity; it is the mathematical backbone of a system that secures billions of transactions every day.