I know that the number 216 + 1 is commonly used for RSA, since 0b 1 0000 0000 0000 0001 only contains two 1 bits. Many sites explain that this makes modular exponentiation faster, but I haven't come across an explanation of why it is faster.
Why is it more efficient to use a number with a lot of zeros for modular exponentiation?
There are a two minor advantages to choosing the exponent 216+1.
The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the basic repeated squaring method is moderately faster when e has lots of zero bits. It is not true that exponents with more one bits are necessarily slower since there are plenty of such numbers with very short addition chains (though finding such short addition chains is an NP complete problem in general). In any case, e = 3 would be a much better choice than e = 216+1 for the sole purpose of exponentiation.
The second advantage is that 216+1 is a prime number and it is not too small. A requirement of the RSA algorithm is that the exponent e must be relatively prime with φ(pq) = (p-1)(q-1). Since the large primes p and q are chosen randomly, there is always a chance that (p-1)(q-1) is not relatively prime with the (previously chosen) exponent e and the primes p,q must therefore be discarded. So small exponents e are poor choices since about every (e-1)th choice of p and q is a bad one, thus shrinking the overall key space. Choosing e to be a large prime would be best, but too large an e would make exponentiation slow. In the end, e = 216+1 is a nice compromise value.
The usually used fast exponentiation algorithm is the so called square-and-multiply-algorithm. It needs exactly n+m multiplications, where n is the total length of the binary written exponent and m is the number of 1-bits in the exponent. Therefore exponentation with 2^16+1 is almost twice as fast as exponentiation with say 2^17-1.
Why is it more efficient to use a number with a lot of zeros for modular exponentiation?
This didn't seem to be answered directly. Optimal addition chain lengths and construction (for say integer $n$) are known when $v(n)$ is small. $v(n)$ is the Hamming weight (number of 1 bits in the binary representation). The length of the smallest addition chain for $n$ is denoted $l(n)$. Simple bounds prove the following addition chain to be optimal: $1,2,4,...,2^{16},2^{16}+1$. If $l(n)=d$ then $n \leq 2^d$ since you can at most double for each step. So $l(2^{16}+1) \geq 17$. The construction of the chain above completes the proof that $l(2^{16}+1)=17$. Now in general the larger $v(n)$ the more non-doubling steps you need in a chain. Doubling does not increase the number of 1's in a number but general multiplies do. Non-doubling steps can at most double the number of ones. We expect that $l(n) \geq \lfloor log_2(n) \rfloor+log_2(v(n))$ but it remains unproven except for small $v(n)$ values and computer searches for $n \leq 2^{64}$ We spit chain steps into two types. With a chain of $1=a_0,a_1,...,a_d=n$ if $\lfloor log_2(a_i) \rfloor= \lfloor log_2(a_{i+1}) \rfloor$ we say step $i$ is a small step. Otherwise it's a large or big step. Calculating optimal addition chains is all about reducing the small steps. We feel that the small step count ($s(n)=l(n)-\lfloor log_2(n) \rfloor$) is a measure of the complexity of $n$. Non-doubling steps eventually add to the small step count since $s(n) \geq f/3.271$ (see Knuth vol 2 4.6.3 Theorem A) with $f$ as the number of non-doubling steps.
