Conway polynomials
 | The CorenSearchBot has performed a web search with the contents of this page, and it appears to include material copied directly from:
It will soon be reviewed to determine if there are any copyright issues. The content should not be mirrored or otherwise reused until the issue has been resolved. If substantial content is duplicated, unless evidence is provided to the contrary (e.g. evidence of permission to use this content under terms consistent with the Wikimedia Terms of Use or public domain status; see Wikipedia:Donating copyrighted materials), editors will assume that this text is a copyright violation, and will soon delete the copy.
Before removing this notice, you should:
|
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(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) = ZZ / pZZ 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) = gn Xn + ... + g0 and h(X) = hn Xn + ... + 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(p^n-1) / (p^m-1)) = 0 mod fp,n(X); that is, the (p^n-1) / (p^m-1)-th power of a zero of fp,n(X) is a zero of fp,m(X).
References:
F. Luebeck's Conway polynomials page, http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html?LANG=en