finfield1 http://www.openmath.org/cd http://www.openmath.org/cd/finfield1.ocd 2004-06-01 1 0 experimental 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>. is_primitive 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. field_by_conway 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). primitive_element 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). is_primitive_poly 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). conway_polynomial 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>. Some Conway polynomials for p = 2. 21 2 1 10 11 22 2 1 10 11 12 23 2 1 10 11 13 24 2 1 10 11 14 25 2 1 10 12 15 26 2 1 10 13 14 16 field_by_conway 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). This field is equal to GF(p)[X]/(c(X)). minimal_polynomial 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. discrete_log 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. later