Choosing the Public Exponent e
You'll learn how to select the encryption exponent that forms half of your RSA public key.
In RSA cryptography, after you've computed φ(n) from your two primes p and q, you need to pick a number e that will serve as your public exponent. This number works with n to form your public key (n, e), which anyone can use to encrypt messages to you.
The Requirements
The exponent e must satisfy two conditions:
- Range: It must be between 1 and φ(n), specifically: 1 < e < φ(n)
- Coprimality: It must be relatively prime to φ(n), meaning gcd(e, φ(n)) = 1
Why coprime? Because later you'll need to find a multiplicative inverse of e modulo φ(n) (called the private exponent d). This inverse only exists when e and φ(n) share no common factors.
Practical Choices
In practice, small prime numbers work well for e. Common choices include:
- e = 3 (fast but requires careful padding)
- e = 65537 = 2^16 + 1 (most popular; balances speed and security)
You must verify that gcd(e, φ(n)) = 1. If your first choice shares a factor with φ(n), simply try another value.
Analogy
Think of e like choosing a lock combination wheel count. You need enough wheels (large enough e) that someone can't trivially guess, but not so many that unlocking (encryption) becomes impractically slow. The coprimality requirement ensures your key actually has a matching "unlock" operation.
Key Takeaway: The public exponent e must be an integer with 1 < e < φ(n) and gcd(e, φ(n)) = 1, making it possible to later compute a private decryption key.