Frank Lübeck |

# Conway polynomials for finite fields

Conway polynomials were defined by R. Parker. Their purpose is to provide a
standard notation for elements in a finite field GF(p^{n}) with
p^{n} elements, p being a prime.

This is for example used within computer algebra systems to have data of finite field elements which can easily be ported between different programs.

The Conway polynomials are also used in data bases like the Modular Atlas character tables, this was the original motivation for their definition.

For n = 1 we have GF(p) = Z / pZ and a standard notation for the elements is given via the representatives 0, ..., p-1 of the cosets modulo p. We order these elements by 0 < 1 < 2 < ... < p-1.

For n > 1 there is a recursive definition. We can write GF(p^{n})
as GF(p)[X] / (f(X)) for some irreducible polynomial f(X)
in GF(p)[X] of degree n.

Before defining which of the possible f(X) is the Conway polynomial we
introduce an ordering of the polynomials of degree n over GF(p).
Let g(X) = g_{n}X^{n} + ... + g_{0} and
h(X) = h_{n}X^{n} + ... + h_{0}.
Then we define g < h if and only if there is an index k with
g_{i} = h_{i} for i > k and (-1)^{n-k}
g_{k} < (-1)^{n-k} h_{k}.

The *Conway polynomial* f_{p,n}(X) for GF(p^{n})
is the smallest polynomial of degree n with respect to this ordering
such that:

- f
_{p,n}(X) is monic - f
_{p,n}(X) is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of GF(p^{n}) - for each proper divisor m of n we have that
f
_{p,m}(X^{(pn-1) / (pm-1)}) = 0 mod f_{p,n}(X); that is, the (p^{n}-1) / (p^{m}-1) -th power of a zero of f_{p,n}(X) is a zero of f_{p,m}(X)

The existence of these polynomials can be shown with the Chinese Remainder Theorem.

For primitivity one checks that for each proper (maximal) divisor k of
p^{n}-1 we have that f_{p,n}(X) does not divide
X^{k}-1. Note that for this the prime divisors of p^{n}-1
are needed. They are known for many p and n from long running integer
factorization projects
which provide their results via the internet, see
Richard
Brent's site for more information on this.

There are basically two methods to compute Conway polynomials.

The first is to run through all polynomials of degree n over GF(p) with respect to the ordering defined above and to check the necessary conditions.

The second possibility is to take any representation of GF(p^{n})
and to enumerate all elements in that field which fulfill the compatibility
condition 3. above. Then check for each of these elements if it is
primitive and if yes compute its minimal polynomial over GF(p). The smallest
polynomial found this way is the Conway polynomial.

Both methods were used by R. Parker to compute a long list of Conway polynomials. These are available in computer algebra systems like GAP or Magma and they are used in several other programs, like the MeatAxe.

From time to time there is need to compute new Conway polynomials, often in
the context of modular representations of larger sporadic groups. This was
also the motivation for this project, more precisely the polynomial for
GF(67^{18}) was needed for some questions concerning the Lyons
simple group.

While the first method described above
is implemented in GAP, the second was not available. The first method is
particularly good when there are few compatibility conditions, that is when
n is prime. (Many polynomials with prime degree n can be easily computed
with GAP as long as p^{n}-1 can be factorized, not all such
polynomials are explicitly contained in the tables on these pages.)

A rough estimate of the computation time of the GAP function for
f_{67,18}(X) was > 10^{10} years.
On the other hand there are about 9 * 10^{10} elements to consider
with the second method. Computing such a number of minimal polynomials can
be actually done, if one uses many computers in parallel.

I have written (in 2001) a parallelized program with a
central server and many client
processes which computes these minimal polynomials and finds the smallest one.
The input for the program is computed with Magma.
Using about 60 computers f_{67,18}(X) could be computed in 12 days.
I then decided to enlarge systematically the list of known Conway
polynomials, starting with such cases which can potentially become
interesting for modular representations of other sporadic simple groups.

In the meanwhile some other people have provided further new Conway polynomials, using both of the mentioned methods. Our tables below contain the precise references.

### References and Acknowledgements

The definition and a long list of Conway polynomials are due to R. Parker. This is not published but the list is floating around for some time and, for example, incorporated in GAP or Magma. All polynomials from Parker's list are now checked with independent programs. (Some lists/systems contained a wrong polynomial for the case p=3, n=21 for some time. But this is now corrected in all systems I'm aware of.)

A formal proof of the existence of Conway polynomials is given in

W. Nickel, *Endliche Körper in dem gruppentheoretischen Programmsystem
GAP*,
Diploma thesis, RWTH Aachen (1988)

The computation method with computing the minimal polynomials of all compatible elements was rediscovered in

L.S.Heath and N.A.Loehr,
*New algorithms for generating Conway polynomials over finite
fields*,
Proceedings of the Tenth Annual ACM-SIAM Symposium on
Discrete Algorithms (Baltimore, MD, 1999), 429--437, ACM, New York (1999)

My computations of new Conway polynomials were done on computers from several networks, sometimes more than 100 machines were working on a single case. The total computation time for the lists given below is roughly a few decades of CPU time. Thanks to the colleagues and administrators for providing the access to these machines. In particular I used machines from:

- 64 x 400MHz PII cluster at the Computer Science Department in St. Andrews, Scotland
- 26 x (2x500MHz) PIII cluster at Computer Science Department, RWTH Aachen, Laboratory for Performance Evaluation and Distributed Systems
- 32 x 400MHz PII Joulian cluster at Computer Science Department, Northeastern University Boston
- 10 x 500MHz PIII pool of Fachbereich Mathematik, RWTH Aachen
- (of course) various machines at Lehrstuhl D für Mathematik, RWTH Aachen

Otherwise idle CPU cylces of the two last mentioned networks (with partially newer and faster machines) are still used for computing a few more polynomials which are just within reach.

Many of the polynomials computed by R. Parker in 2004 were obtained on machines kindly provided by the DPMMS in Cambridge. The needed factorizations in larger characteristic were computed with programs from here.

### The polynomials

Below we provide lists of almost all currently known Conway polynomials.
(As mentioned above some further polynomials with prime degree n can be
easily computed with, say, GAP, as long as the prime factors of
p^{n}-1 can be computed or are known.)
If you know a Conway polynomial with composite n which is missing in these
lists, please tell me!

After each polynomial there is a link to a remark on its origin. Nevertheless, most polynomials were also checked by an independent program.

p = 2 | p = 3 | p = 5 | p = 7 | p = 11 |

p = 13 | p = 17 | p = 19 | p = 23 | p = 29 |

p = 31 | p = 37 | p = 41 | p = 43 | p = 47 |

p = 53 | p = 59 | p = 61 | p = 67 | p = 71 |

p = 73 | p = 79 | p = 83 | p = 89 | p = 97 |

100 < p < 300 |

300 < p < 500 |

500 < p < 1000 |

1000 < p < 10000 |

10000 < p < 20000 |

20000 < p < 30000 |

30000 < p < 40000 |

40000 < p < 60000 |

60000 < p < 110000 |

### Importing these data

All of the above polynomials are available in GAP, at least version 4.4.10. (September 2007)

You can import the data from these pages using this data file (1028 kB, or gzipped version with 219 kB). It has the following format:

- the first line contains
`allConwayPolynomials := [`

- the last line contains
`0 ];`

- other lines have the form
`[p, n, [a0, a1, ..., 1]],`

where`p`

is a prime,`n`

a positive integer and`[a0, a1, ..., 1]`

is a list of integers such that the Conway polynomial f_{p,n}(X) = (`a0`

mod`p`

) + (`a1`

mod`p`

) X + (`a2`

mod`p`

) X^{2}+ ...+ X^{n}.

The file can be read as is into, e.g., GAP or Maple. It should be easy to parse it with other programs, maybe after slight preparation with an editor.

Zuletzt geändert: Di 01.07.2008, 13:14:17 (UTC)