Fast software exponentiation in GF(2/sup k/)

Abstract

The authors present a new algorithm for computing a/sup e/ where a/spl isin/GF(2/sup 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/sup 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.