Fast Exponentiation with Precomputation:
Algorithms and Lower Bounds

Ernest F. Brickell, Daniel M. Gordon
Kevin S. McCurley, and David B. Wilson

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 gn 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 / log2 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