 Conway polynomial (finite fields)

In mathematics, the Conway polynomial C_{p,n} for the finite field F_{pn} is a particular irreducible polynomial of degree n over F_{p} that can be used to define a standard representation of F_{pn} as a splitting field of F_{p}. 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]} and Magma^{[3]}, and at the web site of Frank Lübeck.^{[4]}
Contents
Background
Elements of F_{pn} may be represented as sums of the form a_{n−1}β^{n−1} + ... + 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 nonzero elements of a finite field form a cyclic group under multiplication. A primitive element, α, of F_{pn} is an element that generates this group. Representing the nonzero 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_{pn} (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 F_{pn} are fields F_{pm} with m dividing n. The cyclic group formed from the nonzero elements of F_{pm} is a subgroup of the cyclic group of F_{pn}. If α generates the latter, then the smallest power of α that generates the former is α^{r} where r = (p^{n} − 1)/(p^{m} − 1). If f_{n} is a primitive polynomial for F_{pn} with root α, and if f_{m} is a primitive polynomial for F_{pm}, then by Conway's definition, f_{m} and f_{n} are compatible if α^{r} is a root of f_{m}. This necessitates that f_{m}(x) divide f_{n}(x^{r}). This notion of compatibility is called normcompatibility 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.^{[5]}
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 < ... < p − 1.
 A polynomial of degree d in F_{p}[x] is written a_{d}x^{d} − a_{d−1}x^{d−1} + ... + (−1)^{d}a_{0} and then expressed as the word a_{d}a_{d−1} ... 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.
Computation
Algorithms for computing Conway polynomials that are more efficient than bruteforce search have been developed by Heath and Loehr.^{[6]} Lübeck indicates^{[4]} that their algorithm is a rediscovery of the method of Parker.
Notes
 ^ "GAP 4 Manual". The GAP Group. http://www.gapsystem.org/Manuals//doc/htm/ref/CHAP057.htm#SECT005. Retrieved 8 February 2011.
 ^ Grayson, Daniel R.; Stillman, Michael E.. "Macaulay2, a software system for research in algebraic geometry". http://www.math.uiuc.edu/Macaulay2/doc/Macaulay21.3.1/share/doc/Macaulay2/ConwayPolynomials/html/. Retrieved 9 February 2011.
 ^ Bosma, W.; Steel, A.. "Magma handbook: finite fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney. http://magma.maths.usyd.edu.au/magma/handbook/text/186. Retrieved 8 February 2011.
 ^ ^{a} ^{b} Lübeck, Frank. "Conway polynomials for finite fields". http://www.math.rwthaachen.de/~Frank.Luebeck/data/ConwayPol/index.html. Retrieved 8 February 2011.
 ^ Nickel, Werner (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, Diploma thesis, RWTH Aachen, http://www.mathematik.tudarmstadt.de/~nickel/, retrieved 10 February 2011.
 ^ 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//TR9814, Computer Science. http://eprints.cs.vt.edu/archive/00000493/. Retrieved 8 February 2011.
References
 Holt, Derek F.; Eick, Bettina; O'Brien, Eamonn A. (2005), Handbook of computational group theory, Discrete mathematics and its applications, 24, CRC Press, ISBN 9781584883722
Categories: Finite fields
 Computer algebra
Wikimedia Foundation. 2010.
Look at other dictionaries:
Conway polynomial — In mathematics, Conway polynomial can refer to: the Alexander–Conway polynomial in knot theory the Conway polynomial (finite fields) This disambiguation page lists articles associated with the same title. If an inte … Wikipedia
List of important publications in mathematics — One of the oldest surviving fragments of Euclid s Elements, found at Oxyrhynchus and dated to circa AD 100. The diagram accompanies Book II, Proposition 5.[1] This is a list of important publications in mathematics, organized by field. Some… … Wikipedia
Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… … Wikipedia
General linear group — Group theory Group theory … Wikipedia
Orthogonal group — Group theory Group theory … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… … Wikipedia
Group (mathematics) — This article covers basic notions. For advanced topics, see Group theory. The possible manipulations of this Rubik s Cube form a group. In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines … Wikipedia
mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium
Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity. Computer scientist Manindra Agrawal of the… … Universalium