Computing φ(n) for RSA
You'll learn how to calculate Euler's totient function for RSA's modulus and why it's the secret ingredient that makes encryption work.
What Is φ(n) in RSA?
In RSA, you choose two large prime numbers p and q, then compute their product n = pq. This n becomes your public modulus—everyone can see it. But to create your encryption and decryption keys, you need φ(n), Euler's totient function.
The beautiful simplicity: when n = pq where p and q are distinct primes, then:
φ(n) = (p - 1)(q - 1)
Why This Formula Works
Remember that φ(n) counts how many integers from 1 to n are relatively prime to n. When n is the product of two primes p and q, the only numbers that share a common factor with n are the multiples of p and the multiples of q.
- There are q multiples of p in the range (including p, 2p, ..., pq)
- There are p multiples of q in the range (including q, 2q, ..., pq)
- But we've double-counted pq = n itself
So: φ(n) = n - p - q + 1 = pq - p - q + 1 = (p - 1)(q - 1)
The Role in RSA
Once you have φ(n), you use it to:
- Choose an encryption exponent e that's relatively prime to φ(n)
- Compute the decryption exponent d as the modular inverse of e modulo φ(n)
The critical security point: φ(n) must remain secret. If an attacker knows n but not p and q, they cannot easily compute φ(n)—this is why factoring large numbers is RSA's hardness assumption.
Key Takeaway: For RSA's modulus n = pq, computing φ(n) = (p - 1)(q - 1) is trivial when you know the prime factors, but computationally infeasible when you don't—this asymmetry is RSA's foundation.