Finite field arithmetic has important applications in cryptography and coding theory. In recent years, various efficient algorithms have been developed using the normal basis representation, where every element in GF(qn) is represented in the form a1&bgr;+a2&bgr;2+ ... a2n-1&bgr;2n-1, where each ai ∈ GF(q) and &bgr; ∈ GF(qn).
J. von zur Gathen [1,2] has proposed a parallel algorithm for performing exponentiation on elements in GF(qn), represented in normal basis form in log n+log q time using O(n/logqn) processors. In this paper, the authors present an improvement of von zur Gathen’s algorithm for performing exponentiation in GF(2n) in O(log n) time, using n/(log n)2 processors, thus obtaining optimal processor × time bound O(n/log n).
