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?



modular exponentation for RSA, why is 2^16 + 1 commonly chosen?
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](http://en.wikipedia.org/wiki/Exponentiation_by_squaring) 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](http://en.wikipedia.org/wiki/Addition-chain_exponentiation) (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.


