Conway polynomial (finite fields)

Uniform coding for primitive elements of all finite fields

This article is about a standard set of primitive polynomials for finite fields. For other uses, see Conway polynomial (disambiguation).

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. 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

[edit]

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

## Definition

[edit]

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:

* The elements of Fp are ordered 0 < 1 < 2 < … < p − 1.
* A polynomial of degree d in Fp[x] is written adxd − ad−1xd−1 \+ … + (−1)da0 (with terms alternately added and subtracted) and then expressed as the word ad ad−1 … a0. 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

[edit]

Conway polynomials Cp,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 Fp for small p and small degree.  Degree | F2 | F3 | F5 | F7

|
|
|
|

1 | x \+ 1 | x \+ 1 | x \+ 3 | x \+ 4
2 | x2 \+ x \+ 1 | x2 \+ 2x \+ 2 | x2 \+ 4x \+ 2 | x2 \+ 6x \+ 3
3 | x3 \+ x \+ 1 | x3 \+ 2x \+ 1 | x3 \+ 3x \+ 3 | x3 \+ 6x2 \+ 4
4 | x4 \+ x \+ 1 | x4 \+ 2x3 \+ 2 | x4 \+ 4x2 \+ 4x \+ 2 | x4 \+ 5x2 \+ 4x \+ 3
5 | x5 \+ x2 \+ 1 | x5 \+ 2x \+ 1 | x5 \+ 4x \+ 3 | x5 \+ x \+ 4
6 | x6 \+ x4 \+ x3 \+ x \+ 1 | x6 \+ 2x4 \+ x2 \+ 2x \+ 2 | x6 \+ x4 \+ 4x3 \+ x2 \+ 2 | x6 \+ x4 \+ 5x3 \+ 4x2 \+ 6x \+ 3
7 | x7 \+ x \+ 1 | x7 \+ 2x2 \+ 1 | x7 \+ 3x \+ 3 | x7 \+ 6x \+ 4
8 | x8 \+ x4 \+ x3 \+ x2 \+ 1 | x8 \+ 2x5 \+ x4 \+ 2x2 \+ 2x \+ 2 | x8 \+ x4 \+ 3x2 \+ 4x \+ 2 | x8 \+ 4x3 \+ 6x2 \+ 2x \+ 3
9 | x9 \+ x4 \+ 1 | x9 \+ 2x3 \+ 2x2 \+ x \+ 1 | x9 \+ 2x3 \+ x \+ 3 | x9 \+ 6x4 \+ x3 \+ 6x \+ 4

## Examples

[edit]

To illustrate the definition, let us compute the first six Conway polynomials over F5. 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 F5 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 F5 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, C5,1(x) = x \+ 3.

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

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

Degree 4. The proper divisors of 4 are 1 and 2. Compute (54 − 1) / (52 − 1) = 26 and (54 − 1) / (51 − 1) = 156, and note that 156 / 26 = (52 − 1) / (52 − 1) = 6, the same exponent as appeared in the compatibility condition for degree 2. In degree 4, compatibility requires that C5,4 be chosen so that C5,4(x) divides both C5,2(x26) = x52 \+ 4x26 \+ 2 and C5,1(x156) = x156 \+ 3. The second condition is redundant, however, because of the compatibility condition imposed when choosing C5,2, which implies that C5,2(x26) divides C5,1(x156). 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 C5,2(x26), all of degree 4. All but one are primitive. Of the primitive ones, x4 \+ 4x2 \+ 4x \+ 2 is lexicographically minimal.

Degree 5. The computation is similar to what was done in degrees 2 and 3: (55 − 1) / (51 − 1) = 781; C5,1(x781) = x781 \+ 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 x5 \+ 4x \+ 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 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. The lexicographically least of these is x6 \+ x4 \+ 4x3 \+ x2 \+ 2.

## Computation

[edit]

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

[edit]

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.
5. ^ a b Lübeck, Frank. "Conway polynomials for finite fields". Retrieved 8 February 2011.
6. ^ Coefficients of Cp,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 5d monic polynomials of degree d over F5. For each degree, the number of monic irreducible polynomials over F5 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.

## References

[edit]

* 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