The Number of Irreducible Polynomials over GF(2) with Given Trace and Subtrace

Abstract

The trace of a degree \( n \) polynomial \( p(x) \) over \( \text{GF}(2) \) is the coefficient of \( x^{n-1} \), and the \emph{subtrace} is the coefficient of \( x^{n-2} \). We derive an explicit formula for the number of irreducible degree \( n \) polynomials over \( \text{GF}(2) \) that have a given trace and subtrace. The trace and subtrace of an element \( \beta \in \text{GF}(2^n) \) are defined to be the coefficients of \( x^{n-1} \) and \( x^{n-2} \), respectively, in the polynomial

\[q(x) = \prod_{i=0}^{n-1} (x + \beta^{2^i}).\]

We also derive an explicit formula for the number of elements of \( \text{GF}(2^n) \) of given trace and subtrace. Moreover, a new two-equation Möbius-type inversion formula is proved.