How does the choice of public exponent e affect RSA computation speed?
Smaller e means faster encryption/verification. With $e = 3$, encryption costs only ~1¾t (1 square + 1 multiply); with $e = 65537$, ~13t; with a full-size e, ~3840t (t = one multiplication time).
* Cost tracks the number of 1-bits and the bit-length of e, so 65537 (only two 1-bits) stays cheap while a full-size exponent is ~300x more work. *
Computation cost for different public exponents:
| Public Key $e$ | Binary | SAM Operations | Cost |
|---|---|---|---|
| 3 | $(11)_2$ | 1 SQ + 1 MUL | 1¾t |
| 17 | $(10001)_2$ | 4 SQ + 1 MUL | 4t |
| $65537 = 2^{16}+1$ | $(10...01)_2$ (17 bits) | 16 SQ + 1 MUL | 13t |
| 1024-bit $e$ | ~1024 bits | ~1023 SQ + ~512 MUL | ~1280t |
| 2048-bit $e$ | ~2048 bits | ~2047 SQ + ~1024 MUL | ~2560t |
| 3072-bit $e$ | ~3072 bits | ~3071 SQ + ~1536 MUL | ~3840t |
(where 1 SQ ≈ 0.75 MUL, so $t$ = one multiplication time)
Why $e = 65537 = 2^{16} + 1$ is the standard:
- Only 2 "1" bits in binary → only 1 multiplication besides squarings
- ~295x faster than a random 3072-bit exponent (≈13t vs ≈3840t)
- Still large enough to resist small-exponent attacks on schoolbook RSA
- The Fermat prime $F_4$ — chosen deliberately for this binary structure
Key insight: The public exponent affects encryption and verification speed. The private exponent $d$ (used for decryption and signing) is always large (~3072 bits), so those operations are inherently slower.
Go deeper:
Exponentiation by squaring (Wikipedia) — the square-and-multiply algorithm behind the cost counts.- Fermat number (Wikipedia) — why $65537 = F_4$ has an ideal two-1-bit shape.