Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Fast software exponentiation in GF(2^k)

Cetin K. Koc and Tolga Acar

Abstract

We present a new algorithm for computing ae where a in GF(2k) and e is a positive integer. The proposed algorithm is more suitable for implementation in software, and relies on the Montgomery multiplication in GF(2k). 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.

Details

Publication typeInproceedings
Published in13th Symposium on Computer Arithmetic
URLhttp://www.computer.org/portal/web/csdl/abs/proceedings/arith/1997/7846/00/78460225abs.htm
Pages225–231
OrganizationIEEE Computer Society Press
AddressAsilomar, California
PublisherIEEE Computer Society
> Publications > Fast software exponentiation in GF(2^k)