How do you choose the public exponent e in RSA, and what constraints apply?

e must be coprime with $\varphi(N) = (p-1)(q-1)$, so e must not share factors with $(p-1)$ or $(q-1)$. Common choices: e = 3, 17, or $2^{16}+1 = 65537$.

The requirement: $\gcd(e, \varphi(N)) = 1$

Example: p=7, q=17, N=119, $\varphi(119)=96=2^5 \times 3$

• e must not contain factors 2 or 3
• Valid: e ∈ {5, 7, 11, 13, ...} — there are $\varphi(96) = 32$ possible values
• Excluding 1 and 95 (which shouldn't be used): 30 practical values

Example: p=3, q=11, N=33, $\varphi(33)=20=2^2 \times 5$

• e must not contain factors 2 or 5
• All valid (e, d) pairs: (3,7), (7,3), (9,9), (11,11), (13,17), (17,13), (19,19)
• Note: $e = 9$ is valid even though it's not prime!

Common choices in practice:

• $e = 65537 = 2^{16} + 1$ — most common, good balance of speed and security
• $e = 3$ — fastest for encryption, but vulnerable to certain attacks on "schoolbook" RSA
• Small $e$ is fine for signatures (verification is fast) but dangerous for encryption without padding

Go deeper:

• Fermat number (Wikipedia) — why $65537 = 2^{16}+1 = F_4$ is the popular exponent.
• Euler's totient function (Wikipedia) — the $\varphi(N)$ that $e$ must be coprime to.