Conway polynomial (finite fields)

Elements of F_pⁿ may be represented as sums of the form a_n−1βⁿ⁻¹ + ... + a₁β + a₀ where β is a root of an irreducible polynomial of degree n over F_p and the a_j are elements of F_p. Addition of field elements in this representation is simply vector addition. While there is a unique finite field of order pⁿ up to isomorphism, the representation of the field elements depends on the choice of the irreducible polynomial. The Conway polynomial is a way of standardizing this choice.

The non-zero elements of a finite field form a cyclic group under multiplication. A primitive element, α, of F_pⁿ is an element that generates this group. Representing the non-zero field elements as powers of α allows multiplication in the field to be performed efficiently. The primitive polynomial for α is the monic polynomial of smallest possible degree with coefficients in F_p that has α as a root in F_pⁿ (the minimal polynomial for α). 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 subfields of F_pⁿ are fields F_p^m with m dividing n. The cyclic group formed from the non-zero elements of F_p^m is a subgroup of the cyclic group of F_pⁿ. If α generates the latter, then the smallest power of α that generates the former is α^r where r = (pⁿ − 1)/(p^m − 1). If f_n is a primitive polynomial for F_pⁿ with root α, and if f_m is a primitive polynomial for F_p^m, then by Conway's definition, f_m and f_n are compatible if α^r is a root of f_m. This necessitates that f_m(x) divide f_n(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.[6]

The Conway polynomial C_p,n is defined as the lexicographically minimal monic primitive polynomial of degree n over F_p that is compatible with C_p,m for all m dividing n. This is an inductive definition on n: the base case is C_p,1(x) = x − α where α is the lexicographically minimal primitive element of F_p. The notion of lexicographical ordering used is the following:

• The elements of F_p are ordered 0 < 1 < 2 < ... < p − 1.
• A polynomial of degree d in F_p[x] is written a_dx^d − a_d−1x^d−1 + ... + (−1)^da₀ and then expressed as the word a_da_d−1 ... a₀. 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.

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

• Holt, Derek F.; Eick, Bettina; O'Brien, Eamonn A. (2005), Handbook of computational group theory, Discrete mathematics and its applications, 24, CRC Press, ISBN 978-1-58488-372-2