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.