Optimal same-base exponentiation?
As you suggest, you can speedup the exponentiation using pre-computed values. However, you will face the following problems:


the table with the precomputed values can become rather large, and
the table lookup is in general not constant time.


An example of how these problems can be addressed can be found in the Ed25519 implementation of Bernstein et al.; details are discussed on page 13 of their paper. They use a Brickell exponentiation with a standard trick to reduce the size of the table by 50%, and they use constant-time table lookup (where all possible values are loaded from memory and then combined with logical operations).

Note that because the cost of constant time table lookup is proportional to the size of the table, it is not efficient to represent the exponent as a series of larger chunks (e.g. 16bit->65536 elements in the table). It is more efficient to represent the exponent as a series of smaller chunks (e.g. 4bit).