Public-key cryptographic systems often involve raising elements of som
e group (e.g., GF(2(n)), Z/NZ, or elliptic curves) to large powers. An
important question is how fast this exponentiation can be done, which
often determines whether a given system is practical. The best method
for exponentiation depends strongly on the group being used, the hard
ware the system is implemented on, and whether one element is being ra
ised repeatedly to different powers, different elements are raised to
a fixed power, or both powers and group elements vary. This problem ha
s received much attention, but the results are scattered through the l
iterature. In this paper we survey the known methods for fast exponent
iation, examining their relative strengths and weaknesses. (C) 1998 Ac
ademic Press.