Conway polynomial (finite fields)
Encyclopedia
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 Fp. 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
and Magma
, and at the web site of Frank Lübeck.
, 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 form a cyclic group
under multiplication. A primitive element
, α, of Fpn 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 Fp that has α as a root in Fpn (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 Fpn are fields Fpm with m dividing n. The cyclic group formed from the non-zero elements of Fpm is a subgroup of the cyclic group of Fpn. If α generates the latter, then the smallest power of α that generates the former is αr where r = (pn − 1)/(pm − 1). If fn is a primitive polynomial for Fpn with root α, and if fm is a primitive polynomial for Fpm, then by Conway's definition, fm and fn are compatible if αr is a root of fm. This necessitates that fm(x) divide fn(xr). 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.
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.
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
Fpn is a particular irreducible polynomial
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
of degree n over Fp that can be used to define a standard representation of Fpn as a splitting field
Splitting field
In abstract algebra, a splitting field of a polynomial with coefficients in a field is a smallest field extension of that field over which the polynomial factors into linear factors.-Definition:...
of Fp. Conway polynomials were named after John H. Conway by Richard A. Parker
Richard A. Parker
Richard A. Parker is a mathematician and freelance computer programmer in Cambridge, England. He invented many of the algorithms for computing the modular character tables of finite simple groups...
, 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
GAP computer algebra system
GAP is a computer algebra system for computational discrete algebra with particular emphasis on computational group theory.-History:...
, Macaulay2
Macaulay2
Macaulay2 is a free computer algebra system developed by Daniel Grayson and Michael Stillman for computation in commutative algebra and algebraic geometry. Stillman, along with Dave Bayer had authored the predecessor, Macaulay. Macaulay2 uses its own high level programming language, intended to...
and Magma
Magma computer algebra system
Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma...
, and at the web site of Frank Lübeck.
Background
Elements of Fpn may be represented as sums of the form an−1βn−1 + ... + a1β + a0 where β is a root of an irreducible polynomial of degree n over Fp and the aj are elements of Fp. Addition of field elements in this representation is simply vector addition. While there is a unique finite field of order pn up to isomorphismIsomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
, 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 form a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
under multiplication. A primitive element
Primitive element
In mathematics, the term primitive element can mean:* Primitive root modulo n, in number theory* Primitive element , an element that generates a given field extension...
, α, of Fpn 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
Primitive polynomial
In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF...
for α is the monic polynomial of smallest possible degree with coefficients in Fp that has α as a root in Fpn (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 Fpn are fields Fpm with m dividing n. The cyclic group formed from the non-zero elements of Fpm is a subgroup of the cyclic group of Fpn. If α generates the latter, then the smallest power of α that generates the former is αr where r = (pn − 1)/(pm − 1). If fn is a primitive polynomial for Fpn with root α, and if fm is a primitive polynomial for Fpm, then by Conway's definition, fm and fn are compatible if αr is a root of fm. This necessitates that fm(x) divide fn(xr). 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.
Definition
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 and then expressed as the word adad−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.