## Fast Exponentiation with Precomputation:

Algorithms and Lower Bounds

In several cryptographic systems, a fixed element *g* of a group of
order *N* is repeatedly raised to many different powers. In this
paper we present a practical method of speeding up such systems, using
precomputed values to reduce the number of multiplications needed. In
practice this provides a substantial improvement over the level of
performance that can be obtained using addition chains, and allows the
computation of *g*^{n} for *n<N* in *O(*log* N / *log log* N)*
multiplications. We show that this method is asymptotically optimal
given polynomial storage, and for specific cases, within a small
factor of optimal. We also show how these methods can be
parallelized, to compute powers in time *O(*log log* N)* with *O(*log*
N / *log^{2} log* N)* processors.
An extended abstract of this paper appeared in
*
Advances in Cryptology: Eurocrypt '92*,
Lecture Notes in Computer Science #658, pp. 200-207.

PostScript version