Some remarks on parallel exponentiation (extended abstract)

We present a lower bound on parallel exponentiation in the model of weighted q-addition chains which neglects communication. We derive an algorithm which covers results of Kung [9] and von zur Gathen [13]. For an actual implementation the (fixed) number of processors and the communication delay have to be taken into account. We develop strategies for this scenario—inspired by the results on weighted q-addition chains—for parallel exponentiation using the BSP-model of Valiant [12]. The latter results are illustrated by implementations of different basis representations for finite fields.