|
[____]
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.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|