modular exponentation for RSA, why is 2^16 + 1 commonly chosen?

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?

-
I don't think this is exactly a theoretical question, but I wouldn't mind seeing the answer myself! –  stankewicz Mar 2 '10 at 19:42
I don't think "theoretical" per se is a requirement here. –  Scott Morrison Mar 2 '10 at 21:41
i think this is a fine question, but i do wish that more questions would use correct capitalization. i find it hard to read uncapitalized posts, and it comes across as unprofessional. –  Theo Johnson-Freyd Mar 2 '10 at 23:46
@Theo, I would encourage you to start downvoting with this as a reason. I'll try to as well! "-1, inability to use <shift> key." –  Scott Morrison Mar 3 '10 at 0:51
@Theo, Scott: why not just edit the post? It's not worth editing for tiny grammatical things, but if it's enough for you to leave a comment or a downvote, I think it's better to just edit. –  Anton Geraschenko Mar 3 '10 at 18:23

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.

-
I guess a third advantage of 65537 is that it is the smallest exponent allowed by NIST, though they don't give a specific reason for that choice. (Probably to avoid small exponent attacks, which are possible when proper padding is not used.) –  François G. Dorais Mar 3 '10 at 0:03
@François G. Dorais: If e=3, couldn't you just avoid generating primes that are 1 mod 3? I assume 0 mod 2 and 3 are being avoided already to save some time. It's not hard to take a random number k and consider 6k+5 as a potential prime. –  aorq Mar 3 '10 at 6:41
Yes, that is fine for e=3. It is already difficult for e=5 without further decreasing the key space and/or increasing the key-generation cost. (Note that the real issue with e=3 is the risk of small exponent attacks.) –  François G. Dorais Mar 3 '10 at 14:47
Also, e=3 has the disadvantage that it might be vulnerable to the broadcast attack. If you send a message x using e=3 to 3 different users (with different n_1,n_2,n_3, WLOG, mutually relatively prime (or we'd have a factorisation of 2 of them..) then we could solve x^3 mod n_i (i=1,2,3) using the CRT for x. This is a problem if e=3 were a common exponent. Hence the choice for a relatively large e (also prime and few bits set). –  Henno Brandsma Dec 18 '10 at 10:32
Consider how you might compute something like $5^9$ rapidly. First, compute the numbers $p_0 = 5^{2^0}$, $p_1 = 5^{2^1}$, $p_2 = 5^{2^2}$, and $p_3 = 5^{2^3}$. Each of these is computed from the previous one by squaring, so you have $n-1$ multiplications in total (or $n$ if you start by multiplying 1 by 5 to get $5^{2^0}$). Since 9 is 1001 in binary, you get $5^9$ by multiplying $p_0$ by $p_3$, for $m - 1$ more multiplications (again, $m$ if you start by multiplying 1). In total, we used four multiplications, where you might naively have used nine. –  Matt Noonan Mar 2 '10 at 23:55