Cetin K. Koc and Tolga Acar
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.
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 email@example.com. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
|Organization||IEEE Computer Society Press|