Mathematics
Euler's Totient Function and Its Role in RSA Encryption
Quick fact
Euler's totient function φ(n) counts numbers less than n that have no common factor with n. It is the basis for RSA encryption, where the key math works because φ(n) is easy to compute if you know the prime factors of n, but hard if you don't.
Why this is interesting
You use encryption every day—when you shop online, send a message, or log into an app. But what if the security that protects you depends on a 200-year-old mathematical counting function?
Read the full explanation
Understanding Euler's Totient Function and Its Role in RSA Encryption
In RSA, you start with two large prime numbers, say p and q. Multiply them to get n = pq. Now, Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n—that is, they share no prime factors with n. For primes, φ(p) = p−1 because a prime has no divisors other than 1 and itself. For the product, φ(n) = (p−1)(q−1). This is because the only numbers that are not coprime to n are multiples of p or q, and a simple counting gives (p−1)(q−1).
A deeper explanation
RSA relies on Euler's theorem, which says that if a is coprime to n, then a^φ(n) ≡ 1 (mod n). This theorem is the engine behind RSA. When you choose an encryption key e, you must ensure it has no common factor with φ(n), so you can find a multiplicative inverse d modulo φ(n). Then de = 1 + kφ(n) for some k. When you encrypt a message m as c = m^e mod n, decrypting is c^d mod n = m^(ed) mod n = m^(1+kφ(n)) mod n = m (m^φ(n))^k mod n, which by Euler's theorem equals m. The security comes from the fact that to break RSA, you would need to find φ(n) or factor n into p and q, which is computationally infeasible for large primes. Thus, the totient function is not just a mathematical curiosity; it's the cornerstone of modern secure communication.