Efficient parallel exponentiation in GF(qn) using normal basis representations

Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qn) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qn) can be done in O((log2n)2/logqn) time using n/(log2n)2 processors. Hence we get a processor-time bound of O(n/logqn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.