|
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.
GaloisField(q) : RngIntElt -> FldFin
GF(q) : RngIntElt -> FldFin
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).
GaloisField(p, n) : RngIntElt, RngIntElt -> FldFin
GF(p, n) : RngIntElt, RngIntElt -> FldFin
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.
BaseField(F) : FldFin -> FldFin
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.
To define the field of 7 elements, use
> F7 := FiniteField(7);
We can define the field of 7 4 elements in several different
ways. We can use the Conway polynomial:
> F<z> := FiniteField(7^4);
> F;
Finite field of size 7^4
We 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^4
We can supply our own polynomial, say x 4 + 4x 3 + 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^4
We can define it as an extension of the field of 7 2 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.
Given finite fields E and F, returns whether they are isomorphic (have the same cardinality),
and returns an isomorphism φ : E to F, without implicitly embedding E into 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").
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.
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.
One(F) : FldFin -> FldFinElt
Identity(F) : FldFin -> FldFinElt
Zero(F) : FldFin -> FldFinElt
Representative(F) : FldFin -> FldFinElt
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.
F ! a : FldFin, RngElt -> FldFinElt
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.
Generator(F) : FldFin -> FldFinElt
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.
Seqelt(s, F) : [ FldFinElt ] -> FldFinElt
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.
Eltseq(a) : FldFinElt -> [ FldFinElt ]
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.
Eltseq(a, E) : FldFinElt, FldFin -> [ FldFinElt ]
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|