finfield1 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>. zero This symbol represents a unary function. The argument should be a prime power q. This symbol returns the zero element of GF(q). identity This symbol represents a unary function. The argument should be a prime power q. This symbol returns the identity element of GF(q). 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). conway_polynomial This symbol represents a unary function. Its argument should be a prime power. 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_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 <em>Conway polynomial</em> 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: <ol> <li>f_{p,n}(X) is monic</li> <li>f_{p,n}(X) is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of GF(p^n)</li> <li>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</sub>(X) is a zero of f_{p,m}(X) </li> </ol> 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. <h3>References and Acknowledgements</h3> 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. The computation method with 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. 2 2 10 11 22 2 10 11 12 23 2 10 11 13 24 2 10 11 14 25 2 10 12 15 26 2 10 13 14 16 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 ffe_vector This symbol has two or three arguments. Its first argument should be a finite field element b. Its second argument should be a finite field element x in the field F generated by b. Its optional third argument should be a finite subfield K of F. When applied to b, x and K, the result is a list of n elements [a_0,...,a_{n-1}] from K, where n is the degree of the minimal polynomial of b over K, such that x=a_0+a_1b+...+a_{n-1}b^{n-1}. If there are only two arguments then K is assumed to be the prime field of F. later An element of the Conway field of order 4: 22 1 1 ****deal with the special case of dimension 1 separately***?