Frank Lübeck |
Conway polynomials for finite fields
[Note: There is now an alternative for Conway polynomials which is described in the article:
Lübeck, Frank,
Standard generators of finite fields and their cyclic subgroups.
J. Symbolic Comput.117(2023), 51-67.
(see also https://arxiv.org/abs/2107.02257)
It allows to compute in practice standard generators for many more finite fields, including standardized embeddings (so, it provides an explicit construction of an algebraic closure of each GF(p)). There is also a definition of compatible embeddings of the multiplicative groups of GF(pn) into the complex numbers that can be computed quickly in a much larger range compared to Conway polynomials.]
Conway polynomials were defined by R. Parker. Their purpose is to provide a standard notation for elements in a finite field GF(pn) with pn 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(pn) 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) = gnXn + ... + g0 and h(X) = hnXn + ... + h0. Then we define g < h if and only if there is an index k with gi = hi for i > k and (-1)n-k gk < (-1)n-k hk.
The Conway polynomial fp,n(X) for GF(pn) is the smallest polynomial of degree n with respect to this ordering such that:
- fp,n(X) is monic
- fp,n(X) is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of GF(pn)
- for each proper divisor m of n we have that fp,m(X(pn-1) / (pm-1)) = 0 mod fp,n(X); that is, the (pn-1) / (pm-1) -th power of a zero of fp,n(X) is a zero of fp,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 pn-1 we have that fp,n(X) does not divide Xk-1. Note that for this the prime divisors of pn-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 pages of Richard Brent and Jonathan Crombie 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(pn) 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(6718) 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 pn-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 f67,18(X) was > 1010 years. On the other hand there are about 9 * 1010 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 f67,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 pn-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)
[05/06/2024: added data for a large p, n=1,2,3, for the convenience of sage maintainers.]
You can import the data from these pages using this data file (1328 kB, or gzipped version with 287 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]],
wherep
is a prime,n
a positive integer and[a0, a1, ..., 1]
is a list of integers such that the Conway polynomial fp,n(X) = (a0
modp
) + (a1
modp
) X + (a2
modp
) X2 + ...+ Xn.
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.
Last updated: Mon May 6 17:16:28 2024 (CET)