Picking 'e' for RSA encryption What is the reason behind picking either $3$ or $2^{16}+1$ for generating the public key in RSA?
The cost of computing $x^e \bmod n$, which is the bottleneck in any RSA-based cryptosystem, is $\lfloor\log_2 e\rfloor$ squarings and $H(e) - 1$ multiplications modulo $n$, where $H$ is Hamming weight.*  Since $e$ is required to be coprime with $\operatorname{lcm}(p - 1, q - 1)$, the most efficient possible choice is $e = 3$.†

Originally, the 1977 RSA proposal (which was broken by modern standards in several ways, even ignoring parameter sizes) was to choose $d$ at random and derive $e$ from it.  But there's no security advantage to that, and it's much cheaper to choose $e$ to be small.

Historical RSA-based cryptosystems were badly designed and failed to provide meaningful security: if you naively try to encrypt a message $m$ like a 256-bit secret key by computing $m^e \bmod n$, and $e = 3$, and $\log_2 n &gt; 768$, then it turns out $m^e \bmod n$ is just the integer cube of $m$ and an attacker can recover $m$ from $m^3$ just by computing integer (i.e., real number) cube roots.

So, in an attempt to stem the bleeding of such painfully naive use of RSA like this, people started using bigger exponents like $F_4 = 2^{16} + 1 = 65537$, despite the additional cost it imposes.

The sensible thing to do would be to choose $x$ at random, use a hash of $x$ as a secret key for an authenticated cipher, and transmit $x^3 \bmod n$ alongside the ciphertext—we call this RSA-KEM today.  But because of the decades of RSA abuse, people developed PTSD about small exponents with RSA, and some still break out in a cold sweat when you mention any exponent smaller than 65537.



* For certain exponents the cost may be a little lower with an appropriate choice of Lucas chain, but when $H(e) = 2$ as in $e = 3$ or $e = 2^{16} + 1$ there's not much improvement to be had over the naive square-and-multiply algorithm.

† Rabin-type cryptosystems use modular squaring, or ‘$e = 2$’, but they are qualitatively different from RSA-type cryptosystems.