RSA Fast exponentiation

I am reading a book on cryptography - A mathematical introduction to cryptography (Hoffstein et. al, 1st Edition) and through chapter 3.2, I found this... enter image description here

which describes the RSA system. The author then describes how we could choose $e$.The author says most people who want fast encryption uses $e=2^{16}+1$ as it only takes 4 squarings and one multiplication to compute $m^e$.

I understand the part the it takes one multiplication as $m^{2^{16}+1}=m^{2^{16}}\times m$. But I can not understand how $m^{2^{16}}$ only takes 4 squaring...

I was thinking like this $a_1=m^2$, $a_2=a_1^2=m^4$ , $a_3=a_2^2=m^8$ and $a_4=a_3^2=m^{16}$. This clearly is not correct as $2^{16}\neq16$. Any help would be deeply appreciated.

Solution 1:

Before reading a book, one should look for the errata. In older times, it was hard to get an errata before a second edition. Now, in the internet era, they are collected online, usually from the page of the author

Now the errata says;

Page 121, Line 17

“since it takes only four squarings and one multiplication to compute $m^{65537}$ should be “since it takes only sixteen squarings and one multiplication to compute $m^{65537}$”.

Note that $65537 = 2^{16}+1$ and it is the 4th Fermat prime ($F_4 = 2^{2^4}+1$)

Why do we choose $e$ as a small prime?