Conway polynomial (finite fields)

Elements of \mathbf F_{p^n} may be represented as sums of the form a_{n-1}\beta^{n-1}+\cdots+a_1\beta+a_0 where \beta is a root of an irreducible polynomial of degree n over \mathbf F_{p} and the a_j are elements of \mathbf F_{p}. Addition of field elements in this representation is simply vector addition. While there is a unique finite field of order p^n up to isomorphism, the representation of the field elements depends on the choice of irreducible polynomial. The Conway polynomial is a way of standardizing this choice. The non-zero elements of a finite field \mathbf F form a cyclic group under multiplication, denoted \mathbf F^*. A primitive element, \alpha, of \mathbf F_{p^n} is an element that generates \mathbf F_{p^n}^*. Representing the non-zero field elements as powers of \alpha allows multiplication in the field to be performed efficiently. The primitive polynomial for \alpha is the monic polynomial of smallest possible degree with coefficients in \mathbf F_{p} that has \alpha as a root in \mathbf F_{p^n} (the minimal polynomial for \alpha). It is necessarily irreducible. The Conway polynomial is chosen to be primitive, so that each of its roots generates the multiplicative group of the associated finite field. The field \mathbf F_{p^n} contains a unique subfield isomorphic to \mathbf F_{p^m} for each m dividing n, and this accounts for all the subfields of \mathbf F_{p^n}. For any m dividing n the cyclic group \mathbf F_{p^n}^* contains a subgroup isomorphic to \mathbf F_{p^m}^*. If \alpha generates \mathbf F_{p^n}^*, then the smallest power of \alpha that generates this subgroup is \alpha^r where r=(p^n-1)/(p^m-1). If f_n is a primitive polynomial for \mathbf F_{p^n} with root \alpha and f_m is a primitive polynomial for \mathbf F_{p^m} then, by Conway's definition, f_m and f_n are compatible if \alpha^r is a root of f_m. This necessitates that f_n(x) divide f_m(x^r). This notion of compatibility is called norm-compatibility by some authors. The Conway polynomial for a finite field is chosen so as to be compatible with the Conway polynomials of each of its subfields. That it is possible to make the choice in this way was proved by Werner Nickel. ==Definition==

The Conway polynomial is defined as the lexicographically minimal monic primitive polynomial of degree over that is compatible with for all dividing . This is an inductive definition on : the base case is where is the lexicographically minimal primitive element of . The notion of lexicographical ordering used is the following: • The elements of are ordered . • A polynomial of degree in is written (with terms alternately added and subtracted) and then expressed as the word . Two polynomials of degree d are ordered according to the lexicographical ordering of their corresponding words. Since there does not appear to be any natural mathematical criterion that would single out one monic primitive polynomial satisfying the compatibility conditions over all the others, the imposition of lexicographical ordering in the definition of the Conway polynomial should be regarded as a convention. ==Table==

Conway polynomials for the lowest values of and are tabulated below. All of these were first computed by Richard Parker and were taken from the tables of Frank Luebeck. The calculations can be verified using the basic methods of the next section with the assistance of algebra software. ==Examples==

To illustrate the definition, let us compute the first six Conway polynomials over . By definition, a Conway polynomial is monic, primitive (which implies irreducible), and compatible with Conway polynomials of degree dividing its degree. The table below shows how imposing each of these conditions reduces the number of candidate polynomials. Degree 1. The primitive elements of are 2 and 3. The two degree-1 polynomials with primitive roots are therefore and , which correspond to the words 12 and 13, Since 12 is less than 13 in lexicographic ordering, . Degree 2. Since , compatibility requires that be chosen so that divides . The latter factorizes into three degree-2 polynomials, irreducible over , namely , , and . Of these is not primitive since it divides implying that its roots have order at most 8, rather than the required 24. Both of the others are primitive and is chosen to be the lexicographically lesser of the two. Now corresponds to the word 142 and corresponds to the word 112, the latter being lexicographically less than the former. Hence . Degree 3. Since , compatibility requires that divide , which factorizes as a degree-1 polynomial times the product of ten primitive degree-3 polynomials. Of these, two have no quadratic term, and , which correspond to the words 1032 and 1042. As 1032 is lexicographically less than 1042, . Degree 4. The proper divisors of are and . Compute and , and note that , the same exponent as appeared in the compatibility condition for degree 2. In degree 4, compatibility requires that be chosen so that divides both and . The second condition is redundant, however, because of the compatibility condition imposed when choosing , which implies that divides . In general, for composite degree , the same reasoning implies that only the maximal proper divisors of need be considered, that is, divisors of the form , where is a prime divisor of . There are 13 factors of , all of degree 4. All but one are primitive. Of the primitive ones, is lexicographically minimal. Degree 5. The computation is similar to what was done in degrees 2 and 3: ; has one factor of degree 1 and 156 factors of degree 5, of which 140 are primitive. The lexicographically least of the primitive factors is . Degree 6. Taking into consideration the discussion above in connection with degree 4, the two compatibility conditions that need to be considered are that must divide and . It therefore must divide their greatest common divisor, , which factorizes into 21 degree-6 polynomials, 18 of which are primitive. The lexicographically least of these is . ==Computation==

Algorithms for computing Conway polynomials that are more efficient than brute-force search have been developed by Heath and Loehr. Lübeck indicates that their algorithm is a rediscovery of the method of Parker. ==Notes==