The choice of representation is critical when efficiency of field

arithmetic is critical for your application. For tiny fields, Zech

logarithms can be used, but in most applications field extensions

are represented using some basis. Polynomial bases are referred due to their efficient multiplication, but if exponentiation is required then normal bases should be employed. Unfortunately, no "good" normal basis of GF($2^{64}$) is known, and this field is slightly too large to search exhaustively. In this talk, we present a construction of a new basis for quadratic extensions of binary extension fields, and in particular of GF($2^{64}$), that provides efficient exponentiation along with a great improvement on multiplication complexity.

This is joint work with Colin Weir.