A database of low-term irreducible polynomials for finite fields of small characteristic is available in Magma (see the function IrreducibleLowTermGF2Polynomial below). This database goes up to degree 120,000 for GF(2), and to reasonably high degrees for the fields GF(q) for q up to 128. Thus one can create the finite field GF(pk) for p, k within this range and compute within the field without any delay in the creation. Advantage is also taken of the special form of the defining polynomial.
Previous to V2.11, sparse trinomial/pentanomial irreducible polynomials (see the function IrreducibleSparseGF2Polynomial) were used by default for constructing GF(2k) when k is beyond the Conway range. To enable compatibility with older versions, one may select these sparse polynomials with the parameter Sparse in the creation functions.
Optimize: BoolElt Default: true
Sparse: BoolElt Default: false
Given q = pn, where p is a prime, create the finite field GF(q). If p is very big, it is advised to use the form FiniteField(p, n) described below instead, because Magma will first attempt to factor q completely.The primitive polynomial used to construct GF(q) when n > 1 will be a Conway polynomial, if it is available. If the parameter Optimize is false, then no optimized representation (i.e., by using Zech logarithm tables or internal multi-step extensions) will be constructed for the new field which means that the time to create the field will be trivial but arithmetic operations in the field may be slower -- this is useful if say one wishes to just compute a few trivial operations on a few elements of the field alone.
If q=2k and k is beyond the Conway range, then a low-term irreducible is used (see IrreducibleLowTermGF2Polynomial below). Setting the parameter Sparse to true will cause a sparse polynomial to be used instead if possible (see IrreducibleSparseGF2Polynomial below).
Check: BoolElt Default: true
Optimize: BoolElt Default: true
Sparse: BoolElt Default: false
Given a prime p and an exponent n ≥1, create the finite field GF(pn). The primitive polynomial used to construct GF(q) when n > 1 will be a Conway polynomial, if it is available.By default p is checked to be a strong pseudoprime for 20 random bases b with 1 < b < p; if the parameter Check is false, then no check is done on p at all (this is useful when p is very large and one does not wish to perform an expensive primality test on p).
The parameters are as above.
Optimize: BoolElt Default: true
Sparse: BoolElt Default: false
Given a finite field F and a positive integer n, create an extension G of degree n of F, as well as the embedding map φ : F -> G. The parameter Optimize has the same behaviour as that for the FiniteField function. If F is a default field, then G will also be a default field (so its ground field will be the prime field). Otherwise, the ground field of G will be F.The parameters are as above.
Optimize: BoolElt Default: true
Given a finite field F and a polynomial P of degree n over F, create an extension G=F[α] of degree n of F, as well as the natural embedding map φ : F -> G; the polynomial P must be irreducible over F, and α is one of its roots. Thus the defining polynomial of G over F will be P. The parameter Optimize has the same behaviour as that for the FiniteField function. The ground field of G will be F.The parameter is as above.
Given a finite field F, a literal identifier x, and a polynomial P of degree n over F presented as a (polynomial) expression in x, create an extension G=F[x] of degree n of F, as well as the natural embedding map φ : F -> G; the polynomial P must be irreducible over F, and x is one of its roots. Thus the defining polynomial of G over F will be P. The parameter Optimize has the same behaviour as in the FiniteField function.
Given a finite field F and a degree n, return the extension of F by a random degree-n irreducible polynomial over F.
Given a univariate polynomial P over a finite field F, create the minimal splitting field of P, that is, the smallest-degree extension field G of F such that P factors completely into linear factors over G.
Given a set S of univariate polynomials each over a finite field F, create the minimal splitting field of S, that is, the smallest-degree extension field G of F such that for every polynomial P of S, P factors completely into linear factors over G.
Optimize: BoolElt Default: true
Sparse: BoolElt Default: false
Given a finite field F of cardinality pn and a positive divisor d of n, create a subfield E of F of degree d, as well as the embedding map φ : E -> F.The parameters are as above.
Optimize: BoolElt Default: true
Sparse: BoolElt Default: false
Given a finite field F and an element f of F, create the subfield E of F generated by f, together with the embedding map φ : E -> F. The map and field are constructed so that φ(w)=f, where w is the generator of E (that is, E.1).The parameters are as above.
Given a finite field F, return its ground field. If F was constructed as an extension of the field E, this function returns E; if F was not explicitly constructed as an extension then the prime field is returned.
The subfield of F of prime cardinality.
Returns whether field F is a prime field.
Given finite fields F and G of the same characteristic p, return the finite field that forms the intersection F∩G.
Given finite fields K and L, both of characteristic p, return the smallest field which contains both of them.
> F7 := FiniteField(7);We can define the field of 74 elements in several different ways. We can use the Conway polynomial:
> F<z> := FiniteField(7^4); > F; Finite field of size 7^4We can define it as an extension of the field of 7 elements, using the internal polynomial:
> F<z> := ext< F7 | 4 >; > F; Finite field of size 7^4We can supply our own polynomial, say x4 + 4x3 + 2x + 3:
> P<x> := PolynomialRing(F7); > p := x^4+4*x^3+2*x+3; > F<z> := ext< F7 | p >; > F; Finite field of size 7^4We can define it as an extension of the field of 72 elements:
> F49<w> := ext< F7 | 2 >; > F<z> := ext< F49 | 2 >; > F; Finite field of size 7^4
Given finite fields E and F of cardinality pd and pn, such that d divides n, assert the embedding relation between E and F. That is, an isomorphism between E and the subfield of F of cardinality pd is chosen and set up, and can be used from then on to move between the fields E and F. See [BCS97] for details as to how this is done. If both E and F have been defined with Conway polynomials then the isomorphism will be such that the generator β of F is mapped to α^((pn - 1)/(pd - 1)), where α is the generator of F.
Given finite fields E and F of cardinality pd and pn such that d divides n, as well as an element x∈F, assert the embedding relation between E and F mapping the generator of E to x. The element x must be a root of the polynomial defining E over the prime field. Thus an isomorphism between E and the subfield of F of cardinality pd is set up, and can be used from then on to move between the fields E and F.
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 (the defining polynomial may not be primitive); 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.
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").
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.
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.
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.
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.
Given a finite field F, return the element which has the name attached to it, that is, return the element F.1 of F.
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 over its prime field. Note that it is the responsibility of the user that the map defines a homomorphism.
These generic functions create 1, 1, 0, and 0 respectively, in any finite field.
The generator for F as an algebra over its ground field. Thus, if F was defined by the polynomial P=P(X) over E, so F isomorphic to E[X]/P(X), then F.1 is the image of X in F.If F is a prime field, then 1=1F will be returned.
Given a finite field F create the element specified by a; here a is allowed to be an element coercible into F, which means that a may be
- (i)
- an element of F;
- (ii)
- an element of a subfield of F;
- (iii)
- an element of an overfield of F that lies in F;
- (iv)
- an integer, to be identified with a modulo the characteristic of F;
- (v)
- a sequence of elements of the ground field E of F, of length equal to the degree of F over E. In this case the element a0 + a1w + ... + an - 1wn - 1 is created, where a=[a0, ... an - 1] and w is the generator F.1 of F over E.
Given a finite field F with generator w of degree n over the ground field E, create the element a0 + a1w + ... + an - 1wn - 1∈F, where ai∈E (0≤i≤(n - 1)). If the ai are in some subfield of E or the ai are integers, they will be coerced into the ground field.
Create a `random' element of finite field F.
Given a finite field F, this function returns the element f of F that generates F over its ground field E, so F=E[f]. This is the same as the element F.1.
Given a finite field F and a subfield E of F, this function returns an element f of F that generates F over E, so F=E[f]. Note that this element may be different from the element F.1, but if F.1 works it will be returned.
Given a finite field F, this function returns a primitive element for F, that is, a generator for the multiplicative group F * of F. Note that this may be an element different from the generator F.1 for the field as an algebra. This function will return the same element upon different calls with the same field; the primitive element that is returned is the one that is used as basis for the Log function.
(Procedure.) Given a finite field F and a primitive element x of F, set the internal primitive element p of F to be x. If the internal primitive element p of F has already been computed or set, x must equal it. The function Log (given one argument) returns the logarithm of its argument with respect to the base p; this function thus allows one to specify which base should be used. (One can also use Log(x, b) for a given base but setting the primitive element and using Log(x) will be faster if many logarithms are to be computed.)
Given a finite field F=GF(pn), this function returns a normal element for F over the ground field G, that is, an element α∈F such that α, αq, ..., α^(qn - 1) forms a basis for F over G, where q is the cardinality of G, and n the degree for F over G. Two calls to this function with the same field may result in different normal elements.
Given a finite field F=GF(qn) and a subfield E=GF(q), this function returns a normal element for F over E, that is, an element α∈F such that α, αq, ..., α^(qn - 1) forms a basis for F over E.
Given a sequence s=[s0, ..., sn - 1] of elements of a finite field E, of length equal to the degree of the field F over its subfield E, construct the element s=s0 + s1w + ... + sn - 1wn - 1 of F, where w is the generator F.1 of F over E.
Given an element a of the finite field F, return the sequence of coefficients [a0, ..., an - 1] in the ground field E of F such that a=a0 + a1w + ... + an - 1wn - 1, with w the generator of F over E, and n the degree of F over E.
Given an element a of the finite field F, return the sequence of coefficients [a0, ..., an - 1] in the subfield E of F such that a=a0 + a1w + ... + an - 1wn - 1, with w the generator of F over E, and n the degree of F over E.