We 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 our 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.

PDF file

In  13th Symposium on Computer Arithmetic

Publisher  IEEE Computer Society
Copyright © 2007 IEEE. Reprinted from IEEE Computer Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Details