One major drawback of public-key algorithms is that they are relatively slow. In Sect. 7.5.1 we learned that an acceleration technique is to use short exponents e. Now we study short exponents in this problem in more detail.

2. Most short exponents are of the form e = 2n + 1. Would it be advantageous to use exponents of the form 2n ?1? Justify your answer.

3. Compute the exponentiation xe mod 29 of x = 5 with both variants of e from above for n = 4. Use the square-and-multiply algorithm and show each step of your computation.