Approximating the Number of Irreducible Polynomials over $F_2$ with Several Prescribed Coefficients

Abstract

Let $N(n,t_1,\dots ,t_r)$ be the number of irreducible polynomials of degree $n$ over the finite field ${\mathbb{F}}_2$ where the coefficients of the terms $x^{n-1},\dots ,x^{n-r}$ are prescribed. Finding the exact values for the numbers $N(n,t_1,\dots ,t_r)$ for $r\ge 4$ seems difficult. In this paper, we give an approximation for these numbers. We treat in detail the case $N(n,t_1,\dots ,t_4)$, and we state the approximation in the general case. We experimentally show how good our approximation is.