Efficient parallel exponentiation in 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(qⁿ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qⁿ) can be done in O((log₂n)²/log_qn) time using n/(log₂n)² processors. Hence we get a processor-time bound of O(n/log_qn), 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.