Enumerating irreducible polynomials over the binary field

In this paper, we present an algorithm for enumerating all irreducible polynomials up to a specified degree over the binary field. Our approach is straightforward and avoids the need for testing each polynomial for irreducibility. Consequently, we derive a recursive formula for determining the number of irreducible polynomials of a given degree. While Gauss’s classical formula, which involves the Möbius function, is well known for counting such polynomials, our recursive formula reveals an intriguing connection to Gauss’s result.