In mathematics, the Conway polynomial C_p,n for the finite field F_pⁿ is a particular irreducible polynomial of degree n over F_p that can be used to define a standard representation of F_pⁿ as a splitting field of C_p,n. Conway polynomials were named after John H. Conway by Richard A. Parker, who was the first to define them and compute examples. Conway polynomials satisfy a certain compatibility condition that had been proposed by Conway between the representation of a field and the representations of its subfields. They are important in computer algebra where they provide portability among different mathematical databases and computer algebra systems. Since Conway polynomials are expensive to compute, they must be stored to be used in practice. Databases of Conway polynomials are available in the computer algebra systems GAP, Macaulay2, Magma, SageMath, at the web site of Frank Lübeck, and at the Online Encyclopedia of Integer Sequences.

Elements of ${\displaystyle \mathbf {F} _{p^{n}}}$ may be represented as sums of the form ${\displaystyle a_{n-1}\beta ^{n-1}+\cdots +a_{1}\beta +a_{0}}$ where ${\displaystyle \beta }$ is a root of an irreducible polynomial of degree ${\displaystyle n}$ over ${\displaystyle \mathbf {F} _{p}}$ and the ${\displaystyle a_{j}}$ are elements of ${\displaystyle \mathbf {F} _{p}}$. Addition of field elements in this representation is simply vector addition. While there is a unique finite field of order ${\displaystyle 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 ${\displaystyle \mathbf {F} }$ form a cyclic group under multiplication, denoted ${\displaystyle \mathbf {F} ^{*}}$. A primitive element, ${\displaystyle a}$, of ${\displaystyle \mathbf {F} _{p^{n}}}$ is an element that generates ${\displaystyle \mathbf {F} _{p^{n}}^{*}}$. Representing the non-zero field elements as powers of ${\displaystyle a}$ allows multiplication in the field to be performed efficiently. The primitive polynomial for ${\displaystyle a}$ is the monic polynomial of smallest possible degree with coefficients in ${\displaystyle \mathbf {F} _{p}}$ that has ${\displaystyle a}$ as a root in ${\displaystyle \mathbf {F} _{p^{n}}}$ (the minimal polynomial for ${\displaystyle \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 ${\displaystyle \mathbf {F} _{p^{n}}}$ contains a unique subfield isomorphic to ${\displaystyle \mathbf {F} _{p^{m}}}$ for each ${\displaystyle m}$ dividing ${\displaystyle n}$, and this accounts for all the subfields of ${\displaystyle \mathbf {F} _{p^{n}}}$. For any ${\displaystyle m}$ dividing ${\displaystyle n}$ the cyclic group ${\displaystyle \mathbf {F} _{p^{n}}^{*}}$ contains a subgroup isomorphic to ${\displaystyle \mathbf {F} _{p^{m}}^{*}}$. If ${\displaystyle \alpha }$ generates ${\displaystyle \mathbf {F} _{p^{n}}^{*}}$, then the smallest power of ${\displaystyle \alpha }$ that generates this subgroup is ${\displaystyle \alpha ^{r}}$ where ${\displaystyle r=(p^{n}-1)/(p^{m}-1)}$. If ${\displaystyle f_{n}}$ is a primitive polynomial for ${\displaystyle \mathbf {F} _{p^{n}}}$ with root ${\displaystyle \alpha }$ and ${\displaystyle f_{m}}$ is a primitive polynomial for ${\displaystyle \mathbf {F} _{p^{m}}}$ then, by Conway's definition, ${\displaystyle f_{m}}$ and ${\displaystyle f_{n}}$ are compatible if ${\displaystyle \alpha ^{r}}$ is a root of ${\displaystyle f_{m}}$. This necessitates that ${\displaystyle f_{n}(x)}$ divide ${\displaystyle 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.

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:

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.

Conway polynomials C_p,n for the lowest values of p and n 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.

To illustrate the definition, let us compute the first six Conway polynomials over F₅. 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.