Conway polynomial (finite fields)

Last updated December 07, 2023

In mathematics, the Conway polynomial $C p, n$ for the finite field $F p n$ is a particular irreducible polynomial of degree $n$ over $F p$ that can be used to define a standard representation of $F p n$ 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,^[1] Macaulay2,^[2] Magma,^[3] SageMath,^[4] at the web site of Frank Lübeck,^[5] and at the Online Encyclopedia of Integer Sequences.^[6]

Background

Elements of $F p n$ may be represented as sums of the form $a n -1 β n -1 + \dots + a 1 β + a 0$ 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 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 $F$ form a cyclic group under multiplication, denoted $F *$ . A primitive element, $α$ , of $F p n$ is an element that generates $F * p n$ . 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 n$ (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 field $F p n$ contains a unique subfield isomorphic to $F p m$ for each $m$ dividing $n$ , and this accounts for all the subfields of $F p n$ . For any $m$ dividing $n$ the cyclic group $F * p n$ contains a subgroup isomorphic to $F * p m$ . If $α$ generates $F * p n$ , then the smallest power of $α$ that generates this subgroup is $α r$ where $r = (p n - 1) / (p m - 1)$ . If $f n$ is a primitive polynomial for $F p n$ with root $α$ and $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 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.^[7]

Definition

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 < \dots < p - 1$ .
A polynomial of degree $d$ in $F p [x]$ is written $a d x d - a d -1 x d -1 + \dots + (-1) d a 0$ (with terms alternately added and subtracted) and then expressed as the word $a d a d -1 \dots a 0$ . 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 $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.

Conway polynomials over $F p$ for small $p$ and small degree.
Degree	$F 2$	$F 3$	$F 5$	$F 7$
1	$x + 1$	$x + 1$	$x + 3$	$x + 4$
2	$x 2 + x + 1$	$x 2 + 2 x + 2$	$x 2 + 4 x + 2$	$x 2 + 6 x + 3$
3	$x 3 + x + 1$	$x 3 + 2 x + 1$	$x 3 + 3 x + 3$	$x 3 + 6 x 2 + 4$
4	$x 4 + x + 1$	$x 4 + 2 x 3 + 2$	$x 4 + 4 x 2 + 4 x + 2$	$x 4 + 5 x 2 + 4 x + 3$
5	$x 5 + x 2 + 1$	$x 5 + 2 x + 1$	$x 5 + 4 x + 3$	$x 5 + x + 4$
6	$x 6 + x 4 + x 3 + x + 1$	$x 6 + 2 x 4 + x 2 + 2 x + 2$	$x 6 + x 4 + 4 x 3 + x 2 + 2$	$x 6 + x 4 + 5 x 3 + 4 x 2 + 6 x + 3$
7	$x 7 + x + 1$	$x 7 + 2 x 2 + 1$	$x 7 + 3 x + 3$	$x 7 + 6 x + 4$
8	$x 8 + x 4 + x 3 + x 2 + 1$	$x 8 + 2 x 5 + x 4 + 2 x 2 + 2 x + 2$	$x 8 + x 4 + 3 x 2 + 4 x + 2$	$x 8 + 4 x 3 + 6 x 2 + 2 x + 3$
9	$x 9 + x 4 + 1$	$x 9 + 2 x 3 + 2 x 2 + x + 1$	$x 9 + 2 x 3 + x + 3$	$x 9 + 6 x 4 + x 3 + 6 x + 4$

Examples

To illustrate the definition, let us compute the first six Conway polynomials over $F 5$ . 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.^[8]

Numbers of candidate polynomials over $F 5$ as successive conditions are imposed.
Degree	monic	irreducible	primitive	compatible
1	5	5	2	2
2	25	10	4	2
3	125	40	20	10
4	625	150	48	12
5	3125	624	280	140
6	15625	2580	720	18

Degree 1. The primitive elements of $F 5$ are 2 and 3. 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, $C 5,1 (x) = x + 3$ .

Degree 2. Since $(5 2 - 1) / (5 1 - 1) = 6$ , compatibility requires that $C 5,2$ be chosen so that $C 5,2 (x)$ divides $C 5,1 (x 6) = x 6 + 3$ . The latter factorizes into three degree-2 polynomials, irreducible over $F 5$ , namely $x 2 + 2$ , $x 2 + x + 2$ , and $x 2 + 4 x + 2$ . Of these $x 2 + 2$ is not primitive since it divides $x 8 - 1$ implying that its roots have order at most 8, rather than the required 24. Both of the others are primitive and $C 5,2$ is chosen to be the lexicographically lesser of the two. Now $x 2 + x + 2 = x 2 - 4 x + 2$ corresponds to the word 142 and $x 2 + 4 x + 2 = x 2 - x + 2$ corresponds to the word 112, the latter being lexicographically less than the former. Hence $C 5,2 (x) = x 2 + 4 x + 2$ .

Degree 3. Since $(5 3 - 1) / (5 1 - 1) = 31$ , compatibility requires that $C 5,3 (x)$ divide $C 5,1 (x 31) = x 31 + 3$ , which factorizes as a degree-1 polynomial times the product of ten primitive degree-3 polynomials. Of these, two have no quadratic term, $x 3 + 3 x + 3 = x 3 - 0 x 2 + 3 x - 2$ and $x 3 + 4 x + 3 = x 3 - 0 x 2 + 4 x - 2$ , which correspond to the words 1032 and 1042. As 1032 is lexicographically less than 1042, $C 5,3 (x) = x 3 + 3 x + 3$ .

Degree 4. The proper divisors of $4$ are $1$ and $2$ . Compute $(5 4 - 1) / (5 2 - 1) = 26$ and $(5 4 - 1) / (5 1 - 1) = 156$ , and note that $156 / 26 = (5 2 - 1) / (5 2 - 1) = 6$ , the same exponent as appeared in the compatibility condition for degree 2. In degree 4, compatibility requires that $C 5,4$ be chosen so that $C 5,4 (x)$ divides both $C 5,2 (x 26) = x 52 + 4 x 26 + 2$ and $C 5,1 (x 156) = x 156 + 3$ . The second condition is redundant, however, because of the compatibility condition imposed when choosing $C 5,2$ , which implies that $C 5,2 (x 26)$ divides $C 5,1 (x 156)$ . In general, for composite degree $d$ , the same reasoning implies that only the maximal proper divisors of $d$ need be considered, that is, divisors of the form $d / p$ , where $p$ is a prime divisor of $d$ . There are 13 factors of $C 5,2 (x 26)$ , all of degree 4. All but one are primitive. Of the primitive ones, $x 4 + 4 x 2 + 4 x + 2$ is lexicographically minimal.

Degree 5. The computation is similar to what was done in degrees 2 and 3: $(5 5 - 1) / (5 1 - 1) = 781$ ; $C 5,1 (x 781) = x 781 + 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 $x 5 + 4 x + 3$ .

Degree 6. Taking into consideration the discussion above in connection with degree 4, the two compatibility conditions that need to be considered are that $C 5,6 (x)$ must divide $C 5,2 (x 651) = x 1302 + 4 x 651 + 2$ and $C 5,3 (x 126) = x 378 + 3 x 126 + 3$ . It therefore must divide their greatest common divisor, $x 126 + x 105 + 2 x 84 + 3 x 42 + 2$ , which factorizes into 21 degree-6 polynomials, 18 of which are primitive. The lexicographically least of these is $x 6 + x 4 + 4 x 3 + x 2 + 2$ .

Computation

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

Notes

↑ "Chapter 59". GAP 4 Manual. The GAP Group. Retrieved 8 February 2011.
↑ Grayson, Daniel R.; Stillman, Michael E. "Macaulay2, a software system for research in algebraic geometry". Archived from the original on 20 July 2011. Retrieved 29 November 2023.
↑ Bosma, W.; Steel, A. "Magma handbook: finite fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney. Retrieved 29 November 2023.
↑ "Frank Luebeck's tables of Conway polynomials over finite fields". The Sage Development Team. Retrieved 29 November 2023.
1 2 Lübeck, Frank. "Conway polynomials for finite fields" . Retrieved 8 February 2011.
↑ Coefficients of $C p, n$ for $p = 2$ , 3, 5, 7, and 11 are A141646, A141647, A141648, A141649, and A141749 in the OEIS.
↑ Nickel, Werner (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, Diploma thesis, RWTH Aachen, retrieved 10 February 2011.
↑ There are $5 d$ monic polynomials of degree $d$ over $F 5$ . For each degree, the number of monic irreducible polynomials over $F 5$ is given by A001692 in the OEIS. Numbers of primitive polynomials are given by A027741.
↑ Heath, Lenwood S.; Loehr, Nicholas A. (1998). "New algorithms for generating Conway polynomials over finite fields". Virginia Polytechnic Institute and State University. Technical Report ncstrl.vatech_cs//TR-98-14, Computer Science. Retrieved 8 February 2011.

Related Research Articles

In mathematics, a field $F$ is algebraically closed if every non-constant polynomial in $F [x]$ has a root in $F$ .

An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer coefficients. For example, the golden ratio, $, is an algebraic number, because it is a root of the polynomial x 2 - x - 1 . That is, it is a value for x for which the polynomial evaluates to zero. As another example, the complex number is algebraic because it is a root of x 4 + 4 .$

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, a unique factorization domain (UFD) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an integral domain in which every non-zero non-unit element can be written as a product of irreducible elements, uniquely up to order and units.

In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial whose coefficients are integers. The set of all algebraic integers $A$ is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers.

In abstract algebra, a splitting field of a polynomial with coefficients in a field is the smallest field extension of that field over which the polynomial splits, i.e., decomposes into linear factors.

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial $x 2 - 2$ is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as $if it is considered as a polynomial with real coefficients. One says that the polynomial x 2 - 2 is irreducible over the integers but not over the reals.$

In algebra, a monic polynomial is a non-zero univariate polynomial in which the leading coefficient is equal to 1. That is to say, a monic polynomial is one that can be written as

In field theory, a branch of algebra, an algebraic field extension $is called a separable extension if for every, the minimal polynomial of over F is a separable polynomial. There is also a more general definition that applies when E is not necessarily algebraic over F . An extension that is not separable is said to be inseparable .$

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, Eisenstein's criterion gives a sufficient condition for a polynomial with integer coefficients to be irreducible over the rational numbers – that is, for it to not be factorizable into the product of non-constant polynomials with rational coefficients.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

In mathematics, a monomial order is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e.,

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field $GF(p m)$ . This means that a polynomial $F (X)$ of degree $m$ with coefficients in $GF(p) = Z / p Z$ is a primitive polynomial if it is monic and has a root $α$ in $GF(p m)$ such that $is the entire field GF(p m) . This implies that α is a primitive (p m - 1)-root of unity in GF(p m) .$

In algebra, given a polynomial

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In field theory, a branch of mathematics, the minimal polynomial of an element $α$ of a field extension is, roughly speaking, the polynomial of lowest degree having coefficients in the field, such that $α$ is a root of the polynomial. If the minimal polynomial of $α$ exists, it is unique. The coefficient of the highest-degree term in the polynomial is required to be 1.

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Chapter 59". GAP 4 Manual. The GAP Group. Retrieved 8 February 2011.

[2] Grayson, Daniel R.; Stillman, Michael E. "Macaulay2, a software system for research in algebraic geometry". Archived from the original on 20 July 2011. Retrieved 29 November 2023.

[3] Bosma, W.; Steel, A. "Magma handbook: finite fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney. Retrieved 29 November 2023.

[4] "Frank Luebeck's tables of Conway polynomials over finite fields". The Sage Development Team. Retrieved 29 November 2023.

[FOOTNOTESLuebeck-5] 1 2 Lübeck, Frank. "Conway polynomials for finite fields" . Retrieved 8 February 2011.

[6] Coefficients of $C p, n$ for $p = 2$ , 3, 5, 7, and 11 are A141646, A141647, A141648, A141649, and A141749 in the OEIS.

[7] Nickel, Werner (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, Diploma thesis, RWTH Aachen, retrieved 10 February 2011.

[8] There are $5 d$ monic polynomials of degree $d$ over $F 5$ . For each degree, the number of monic irreducible polynomials over $F 5$ is given by A001692 in the OEIS. Numbers of primitive polynomials are given by A027741.

[9] Heath, Lenwood S.; Loehr, Nicholas A. (1998). "New algorithms for generating Conway polynomials over finite fields". Virginia Polytechnic Institute and State University. Technical Report ncstrl.vatech_cs//TR-98-14, Computer Science. Retrieved 8 February 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]