Magma provides a powerful environment for computing with lattices of finite fields. Complete freedom in the manner in which fields are constructed is allowed, while assuring compatibility. Finite fields of various kinds are supported, with optimized representations for each kind. For a detailed description of how finite fields are presented in Magma, see [BCS97].
In Magma, arithmetic in small non-prime finite fields is carried out using tables of Zech logarithms. While this ensures that finite field arithmetic is fast, its use is limited to finite fields of small cardinality.
Larger finite fields are internally represented as polynomial rings over a small finite field. It is possible for the user to specify his own irreducible polynomial (although internally an alternative representation may well be used).
Although two finite fields of the same cardinality are isomorphic, in practical applications it is often important to be guaranteed to work in a field defined by a specific polynomial. Moreover, in passing between fields and subfields, choices regarding the embeddings have to be made, so that these embeddings are compatible (so that `diagrams commute'). The scheme implemented in Magma and described in [BCS97] ensures that this is so.
To avoid ambiguities when talking about (small) finite fields, Conway polynomials have been defined and calculated by R. Parker. The Conway polynomial Cp, n is the lexicographically first monic irreducible, primitive polynomial of degree n over GF(p) with the property that it is consistent with all Cp, m for m dividing n. Consistency of Cp, n and Cp, m for m dividing n means that for a root α of Cp, n it holds that β = α^((pn - 1)/(pm - 1)) is a root of Cp, m. Lexicographically first is with respect to the system of representatives -((p - 1)/2), ..., - 1, 0, 1, ..., ((p - 1)/2) for the residue classes modulo p, ordered via 0 < - 1 < 1 < - 2 < ... ((p - 1)/2) (and we only need to compare polynomials of the same degree).
To compute the Conway polynomial Cp, n one needs to know all Conway polynomials Cp, m for m dividing n, and as far as we know, no essentially better method is known than enumerating and testing the primitive polynomials of degree n in lexicographical order.
Conway polynomials are used in Magma by default for the construction of GF(pn) using FiniteField(p, n) or its synonyms, whenever the Conway polynomial is available. However, it must be stressed that Conway polynomials are only used in Magma to provide standard defining polynomials for GF(pn) -- the special properties of Conway polynomials are never used because they are totally irrelevant in the scheme implemented in Magma!
Throughout this Chapter we will use the notions of ground field and prime field in the following way. The prime field of a finite field F is the unique field of cardinality p, the characteristic of F. Here we mean unique not just in the mathematical sense, but in the sense that all prime fields of the same cardinality are identical in Magma, and their elements are denoted 0, 1, ..., p - 1. The ground field of F is the field over which F is created as an extension. If F was not explicitly created as an extension of a finite field E by using ext, its ground field will be the prime field. Printing in Magma always takes place with respect to the ground field, that is, elements of F are expressed as polynomials in the generator F.1 of the field with coefficients in the ground field; there is one exception to this rule: if the field F is small enough to be represented by means of Zech logarithms, the printing of elements is in the form of powers of the primitive element (see the option on AssertAttribute below for ways of changing that).
It should be kept in mind that finite fields may be related mathematically without Magma being aware of the relation between them. This happens for example when two fields of dividing degrees are created as extensions of one field; although an isomorphic image of the smaller field will be contained in the larger, Magma will not establish this relation (unless the user explicitly asks for it, using the Embed function). However, all subfields of one common overfield in Magma will have their inclusion relations set up automatically.