Fast software exponentiation in GF(2k)

The authors present a new algorithm for computing $a^e$ where $a \in GF(2^k)$ and $e$ is a positive integer. The proposed algorithm is more suitable for implementation in software, and relies on the Montgomery multiplication in $GF(2^k)$. The speed of the exponentiation algorithm largely depends on the availability of a fast method for multiplying two polynomials of length $w$ defined over GF(2). The theoretical analysis and experiments indicate that the proposed exponentiation method is at least 6 times faster than the exponentiation method using the standard multiplication when $w=8$. Furthermore, the availability of a 32-bit GF(2) polynomial multiplication instruction on the underlying processor would make the new exponentiation algorithm up to 37 times faster.