Efficient parallel exponentiation in GF(2n) using normal basis representations

摘要

Vonzur 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(2 ⁿ ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(2 ⁿ ) can be done in &Ogr;(log n) time using n/(log n)² processors. Hence we get processor x time bound &Ogr;(n/log n), which is optimal. Finally, we present an on-line processor assignment scheme which was missing in von zur Gathen's algorithm, and show that its time complexity is negligible.