Processor-efficient exponentiation in finite fields (Q1186580)

This paper studies the number of processors used for parallel exponentiation in a finite field. It is assumed that a normal basis over the base field is given. The algorithms presented only consider multiplication, and computation of \(q\)-th power is assumed to have zero cost. Here \(q\) is a prime power and the finite field in question is \({\mathbb{F}}_{q^ n}\). Three measurements are used for considering the efficiency of the algorithm: The depth (parallel time), the size (total work), and the width (number of processors). At the end of the paper the algorithm is discussed under the assumption that only few processors are available.