From: mareg@mimosa.csv.warwick.ac.uk ()
Subject: Re: Conway Polynomials
Date: 23 Nov 2000 16:44:23 GMT
Newsgroups: sci.math
Summary: [missing]

In article <3A1C3E7C.132B3621@vnet.ibm.com>,
	Andrei Heilper <aheilper@vnet.ibm.com> writes:
>The computational algebra packages GAP and Magma are using a special
>primitive polynomial which they call the Conway polynomial. They are
>used are as canonical generators of the Galois fields.
>
>Does anybody have any references to papers dealing with these
>polynomials?
>(Apparently there are Conway polynomials in knot theory, but they seem
>to be something different).
>
>Andrei Heilper
>

I do not believe that there are any papers dealing with the Conway
polynomials used as canonical generators of Galois fields. They are
defined int GAP and Magma manuals. All they really provide is a
clear cut method of specifying uniquely a convenient polynomial to
use to define the fields. There probably isn't really enough to say
about them to justify writing a paper about them!

Here is the definition quoted verbatim from "An ATLAS of Brauer Characters",
by C. Jansen, K. Lux, R. Parker & R. Wilson, Oxford Univ. Press, 1995.


Conway Polynomials

Up to isomorphism there is a unique field GF(q) of order q=p^n for each
prime p and for each positive integer n. The field GF(p) is just the
field Z/pZ of integers modulo p. The field GF(q) may then be defined as
GF(p)[X]/(f_n) where f_n is an irreducible polynomial of degree n. Note
that there are many such polynomials. We choose one, called the Conway
polynomial, which has particularly nice properties.

First we specify that f_n is a monic and primitive polynomial, which means
that z_n = X + (f_n) is a generator for the multiplicative group GF(q)*
of GF(q). Second, to ensure consistency with subfields, we insist that,
for each d dividing n, if alpha = (p^n - 1)/(p^d - 1), then (z_n)^alpha
is a root of f_d.

Then we define an ordering on the monic polynomials of degree n over GF(p)
given by mapping the polynomial
      x^n - a_{n-1}X^{n-1} + ... + (-1)^n a_0
to the word   a_{n-1},a_{n-2},a_{n-3},...,a_0,  and taking the
lexicographic ordering on these words induced from the ordering
0 < 1 < 2 < ... < p-1  on GF(p). The n-th Conway polyunomial C_n is now
defined as the smallest polynomial of degree  n (with respect to this
ordering) which satisfies the above conditions.

It is not obvious that such polynomials exist for all n but this is proved
in Nickel (1988). This choice means that the lift of an element of the
algebraic closure of GF(p). This choice means that the lift of an element
of the algebraic closure of GF(p) is independent of the finite field that
it is considered to belong to.

Nickel, W. (1988). Endliche Koerper in dem gruppentheoretischen
Programmsystem GAP. Diplomarbiet, RWTH AAchen.


Derek Holt.