3.6 Powers of Trace Functions

In this section, we will describe how to compute a power of a trace function and give a formula for the exponents in the expansion. This expansion has important applications for computing linear spans of GMW sequences, generalized GMW sequences, bent function sequences, geometric sequences, and so on.

Let p be a prime, q = p ^r, and let f( x) be a function from GF( q ⁿ) to GF( q). By the Lagrange interpolation formula and , for x ? GF( q ⁿ), we can write f( x) in a polynomial form (we will discuss this representation in detail in Chapter 6). The weight of f( x), denoted as w( f), is defined as the number of nonzero coefficients of f( x); that is,

Any number in can be written as a number in the p-ary number system. In other words, for x ? , we can write it as , 0 ? x _i < p. The Hamming weight of x, as a p-ary number, is defined as the number of nonzero coefficients of x with respect to the base {1, p, ,p ^{t 1}}; that is, w( x) = { i x _i ? 0, 0 ? i < t}. For , , 0