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.