In mathematics, the Conway polynomial Cp,n for the finite field Fpn is a particular irreducible polynomial of degree n over Fp that can be used to define a standard representation of Fpn as a splitting field of Cp,n.
Databases of Conway polynomials are available in the computer algebra systems GAP,[1] Macaulay2,[2] Magma,[3] SageMath,[4] at the web site of Frank Lübeck,[5] and at the Online Encyclopedia of Integer Sequences.
The non-zero elements of a finite field F form a cyclic group under multiplication, denoted F*.
The Conway polynomial is chosen to be primitive, so that each of its roots generates the multiplicative group of the associated finite field.
[7] The Conway polynomial Cp,n is defined as the lexicographically minimal monic primitive polynomial of degree n over Fp that is compatible with Cp,m for all m dividing n. This is an inductive definition on n: the base case is Cp,1(x) = x − α where α is the lexicographically minimal primitive element of Fp.
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.
The calculations can be verified using the basic methods of the next section with the assistance of algebra software.
The table below shows how imposing each of these conditions reduces the number of candidate polynomials.
The two degree-1 polynomials with primitive roots are therefore x − 2 = x + 3 and x − 3 = x + 2, which correspond to the words 12 and 13, Since 12 is less than 13 in lexicographic ordering, C5,1(x) = x + 3.
Taking into consideration the discussion above in connection with degree 4, the two compatibility conditions that need to be considered are that C5,6(x) must divide C5,2(x651) = x1302 + 4x651 + 2 and C5,3(x126) = x378 + 3x126 + 3.
It therefore must divide their greatest common divisor, x126 + x105 + 2x84 + 3x42 + 2, which factorizes into 21 degree-6 polynomials, 18 of which are primitive.
Algorithms for computing Conway polynomials that are more efficient than brute-force search have been developed by Heath and Loehr.