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 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