OpenMath is an extensible standard for representing the semantics of mathematical objects.
OpenMath is an extensible standard for representing the semantics of mathematical objects.
A CD to instantiate finite fields.
Built by Arjeh M. Cohen 2003-02-25.
The information on Conway polynomials is largely taken from
<a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/">Frank Luebeck</a>.
This symbol represents a binary Boolean function. The first argument should be a finite field, the second a an element of that field. When applied to such arguments, the value represented is true if the second argument is a primitive element of the field, that is, a generator of the multiplicative group of the field.
| [Next: field_by_conway] [Last: discrete_log] [Top] |
This symbol represents a binary function. The first argument should be a prime number p, the second argument a positive integer n. This symbol returns the field GF(q)[X]/ (C(X)), where q = p^n, X is an indeterminate, C(X) is the Conway polynomial f_{n,p}(X), and (C(X)) is the ideal in the polynomial ring GF(q)[X] generated by C(X).
| [Next: primitive_element] [Previous: is_primitive] [Top] |
This symbol has one or two arguments. If there is only one argument, it must be a prime power q. The optional second argument is a polynomial m which is primitive over the prime subfield of GF(q). This symbol returns a primitive element for GF(q) with minimal polynomial m. If there is only one argument, then the minimal polynomial is assumed to be the conway polynomial for GF(q).
| [Next: is_primitive_poly] [Previous: field_by_conway] [Top] |
This symbol is a Boolean-valued function with two arguments, the first of which should be a prime number p, and the second of which should be a polynomial with coefficients in GF(p). When applied to p and f, this symbol represents the value true if and only if f is a primitive polynomial, that is, f is irreducible over GF(p), so GF(p)[X]/(f) is a finite field of order p^n, where n is the degree of f, and the image of X in GF(p)[X]/(f) is a generator of the (cyclic) multiplicative group of GF(p)[X]/(f).
| [Next: conway_polynomial] [Previous: primitive_element] [Top] |
This symbol represents a binary function. Its arguments should be a prime number p and a positive integer n.
Before defining which of the possible f(X) is the Conway polynomial we introduce an ordering of the (univariate) polynomials of degree n over GF(p). Here the coefficients of the polynomials are taken in {0, ..., p-1}, the indeterminate is X. Let g(X) = g_nX^n + ... + g_0 and h(X) = h_nX^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 defined recursively as the smallest polynomial of degree n with respect to this ordering such that: 1) f_{p,n}(X) is monic,
2) f_{p,n}(X) is primitive, that is, it is irreducible and its zeros are generators of the (cyclic) multiplicative group of GF(p^n),
3) for each proper divisor m of n we have that f_{p,m}(X^{(p^n-1) / (p^m-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, see W. Nickel, <em>Endliche Koerper in dem
gruppentheoretischen Programmsystem GAP</em>, Diploma thesis, RWTH
Aachen (1988)
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.
The computation method of computing the minimal polynomials of all
compatible elements was rediscovered in
L.S.Heath and N.A.Loehr, <em>New algorithms for generating Conway
polynomials over finite fields</em>, Proceedings of the Tenth Annual
ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999),
429--437, ACM, New York (1999)
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 (for primitivity one has to check that for each proper
(maximal) divisor k of p^n-1 we have that f_{p,n}(X)
does not divide X^k-1).
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 <a
href="http://www.gap-system.org">GAP</a> or <a
href="http://www.maths.usyd.edu.au:8000/u/magma/">Magma</a> and they
are used in several other programs, like the <a
href="http://www.math.rwth-aachen.de/~MTX/">MeatAxe</a>.
| [Next: field_by_conway] [Previous: is_primitive_poly] [Top] |
This symbol has two arguments. Its first argument should be a prime number p and its second argument a positive integer n. When applied to p and n, the result is the field defined as the quotient ring GF(p)[X]/(c(X)), where c(X)=conway_polynomial(p,n).
| [Next: minimal_polynomial] [Previous: conway_polynomial] [Top] |
This symbol represents a function with one or two arguments. Its first argument should be an element x of a finite field F. The second argument should be a subfield K of F. It returns the minimal polynomial of x over K. If there is only one argument, K defaults to the prime subfield of F.
| [Next: discrete_log] [Previous: field_by_conway] [Top] |
This symbol represents a binary function. The first argument is the base b, a primitive element of a finite field F. The second argument is a nonzero element x in F. It returns the smallest nonnegative integer i such that x=b^i.
| [First: is_primitive] [Previous: minimal_polynomial] [Top] |