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 \in \{5, 7, 11, 13, \dots\}$ — 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.