Counting Irreducible Polynomials of Degree over and Generating Goppa Codes Using the Lattice of Subfields of

The problem of finding the number of irreducible monic polynomials of degree over is considered in this paper. By considering the fact that an irreducible polynomial of degree over has a root in a subfield of if and only if , we show that Gauss’s formula for the number of monic irreducible polynomials can be derived by merely considering the lattice of subfields of . We also use the lattice of subfields of to determine if it is possible to generate a Goppa code using an element lying in a proper subfield of . 1. Introduction In this paper we consider the problem of finding the number, , of monic irreducible polynomials of degree over the field , where is a positive integer and is the power of a prime number. This problem has been discussed by several authors including C. F. Gauss who gave the following beautiful formula: where runs over the set of all positive divisors of including 1 and and is the M？bius function; see [1]. Recently, it has been shown, see [2], that this number can be found by using only basic facts about finite fields and the Principle of Inclusion-Exclusion. This work seeks to emphasize the simplicity of the method given in [2] by using a lattice of subfields. This is done by first of all proving Gauss’s formula using the Principle of Inclusion-Exclusion as was done in [2]. However, we use only one basic fact about where (in which subfields) the roots of irreducible polynomials of degree over can lie. We then show how a lattice of subfields of the field, , can be used to obtain . We are particularly interested in the number of roots of irreducible polynomials of degree over because the problem of counting irreducible Goppa codes of length and of degree depends on this number. 2. Preliminaries 2.1. The Number of Irreducible Polynomials Our approach to counting the number of irreducible polynomials of degree over is to count the number of all roots of such polynomials. To this end, we make the following definitions. Definition 1. One defines the set to be the set of all elements in of degree over . Definition 2. One defines the set to be the set of all irreducible monic polynomials of degree over . The following theorem is well known. Theorem 3. is given by formula (1). For the sake of clarity we state the relationship between and which immediately leads to the “Gaussian like” count of the number of elements in . We put this in the following corollary. Corollary 4. is the union of all the roots of the polynomials in and 2.2. Where Elements of Lie We next identify the subfields of where the elements of lie. To achieve this we first note