[Next] [Prev] [Right] [____] [Up] [Index] [Root]
Introduction

Introduction

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 [W. Bosma, J. Cannon and A. Steel, Lattices of Compatibly Embedded Finite Fields, J. Symb. Comp. 24 (1997), pp. 351--369.].

Subsections

Representation of Finite Fields

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, and in particular it is desirable that `diagrams commute'. To avoid ambiguities when talking about (small) finite fields, Conway polynomials have been defined and calculated by R. Parker. The Conway polynomial C_(p, n) is the lexicographically first monic irreducible, primitive polynomial of degree n over GF(p) with the property that it is consistent with all C_(p, m) for m dividing n. Consistency of C_(p, n) and C_(p, m) for m dividing n means that for a root alpha of C_(p, n) it holds that beta = alpha^((p^n - 1)/(p^m - 1)) is a root of C_(p, 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 C_(p, n) one needs to know all Conway polynomials C_(p, 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(p^n) using FiniteField(p, n) or its synonyms, whenever the Conway polynomial is available.

Ground Field and Relationships

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.

Homomorphisms

hom< F -> G | x > : FldFin, Rng -> Map
Given a finite field F, create a homomorphism with F as its domain and G as its codomain. If F is a prime field, then the right hand side in the constructor must be empty; in this case the ring homomorphism is completely determined by the rule that the map must be unitary, that is, 1 of F is mapped to 1 of G. If F is not of prime cardinality, then the homomorphism must be specified by supplying one element x in the codomain, which serves as the image of the generator of the field F. Note that it is the responsibility of the user that the map defines a homomorphism.

Special Options

For finite fields for which the complete table of Zech logarithms is stored (and which must therefore be small), printing of elements can be done in two ways: either as powers of the primitive element or as polynomials in the generating element.

Note that power printing is not available in all cases where the logarithm table is stored however; for convenience element of a prime field are always printed as integers, and therefore power printing on prime fields will not work. Also, if a field is created with a generator that is not primitive, then power printing will be impossible.

AssertAttribute(FldFin, "PowerPrinting", l) : Cat, MonStgElt, BoolElt ->
This attribute is used to change the default printing for all (small) finite fields created after the AssertAttribute command is executed. If l is true all elements of finite fields small enough for the Zech logarithms to be stored will be printed by default as a power of the primitive element -- see PrimitiveElement). If l is false every finite field element is printed by default as a polynomial in the generator F.1 of degree less than n over the ground field. The default can be overruled for a particular finite field by use of the AssertAttribute option listed below. The value of this attribute is obtained by use of HasAttribute(FldFin, "PowerPrinting").
SetPowerPrinting(F, l) : FldFin, BoolElt ->
AssertAttribute(F, "PowerPrinting", l) : FldFin, MonStgElt, BoolElt ->
Given a finite field F, the Boolean value l can be used to control the printing of elements of F, provided that F is small enough for the table of Zech logarithms to be stored. If l is true all elements will be printed as a power of the primitive element -- see PrimitiveElement). If l is false (which is the only possibility for big fields), every element of F is printed as a polynomial in the generator F.1 of degree less than n over the ground field of F, where n is the degree of F over its ground field. The function HasAttribute(F, "PowerPrinting") may be used to obtain the current value of this flag.
HasAttribute(FldFin, "PowerPrinting", l) : Cat, MonStgElt, BoolElt ->
This function is used to find the current default printing style for all (small) finite fields. It returns true (since this attribute is always defined for FldFin), and also returns the current value of the attribute. The procedure AssertAttribute(FldFin, "PowerPrinting", l) may be used to control the value of this flag.
HasAttribute(F, "PowerPrinting") : FldFin, MonStgElt -> BoolElt, BoolElt
Given a finite field F that is small enough for the table of Zech logarithms to be stored, returns true if the attribute "PowerPrinting" is defined, else returns false. If the attribute is defined, the function also returns the value of the attribute. The procedure AssertAttribute(F, "PowerPrinting", l) may be used to control the value of this flag.
AssignNames(~F, [f]) : FldFin, [ MonStgElt ]) ->
Procedure to change the name of the generating element in the finite field F to the contents of the string f. When F is created, the name will be F.1.

This procedure only changes the name used in printing the elements of F. It does not assign to an identifier called f the value of the generator in F; to do this, use an assignment statement, or use angle brackets when creating the field.

Note that since this is a procedure that modifies F, it is necessary to have a reference ~F to F in the call to this function.

Name(F, 1) : FldFin, RngIntElt -> FldFinElt
Given a finite field F, return the element which has the name attached to it, that is, return the element F.1 of F.
[Next] [Prev] [Right] [____] [Up] [Index] [Root]