Finite fields comprise an important algebraic domain. The elements in a field form an additive group and the nonzero elements form a multiplicative group. For every prime power q there exists a unique field of size q up to isomorphism. GAP3 supports finite fields of size at most 216.
The first section in this chapter describes how you can enter elements of finite fields and how GAP3 prints them (see Finite Field Elements).
The next sections describe the operations applicable to finite field elements (see Comparisons of Finite Field Elements and Operations for Finite Field Elements).
The next section describes the function that tests whether an object is a finite field element (see IsFFE).
The next sections describe the functions that give basic information about finite field elements (see CharFFE, DegreeFFE, and OrderFFE).
The next sections describe the functions that compute various other representations of finite field elements (see IntFFE and LogFFE).
The next section describes the function that constructs a finite field (see GaloisField).
Finite fields are domains, thus all set theoretic functions are applicable to them (see chapter Domains and Set Functions for Finite Fields).
Finite fields are of course fields, thus all field functions are applicable to them and to their elements (see chapter Fields and Field Functions for Finite Fields).
All functions are in LIBNAME/"finfield.g"
.
Z( p^d )
The function Z
returns the designated generator of the multiplicative
group of the finite field with p^d
elements. p must be a prime
and p^d
must be less than or equal to 216 = 65536.
The root returned by Z
is a generator of the multiplicative group of
the finite field with pd elements, which is cyclic. The order of the
element is of course pd-1. The pd-1 different powers of the root
are exactly the nonzero elements of the finite field.
Thus all nonzero elements of the finite field with p^d
elements
can be entered as Z(p^d)^i
. Note that this is also the form
that GAP3 uses to output those elements.
The additive neutral element is 0*Z(p)
. It is different from the
integer 0
in subtle ways. First IsInt( 0*Z(p) )
(see IsInt) is
false
and IsFFE( 0*Z(p) )
(see IsFFE) is true
, whereas it is
just the other way around for the integer 0.
The multiplicative neutral element is Z(p)^0
. It is different from
the integer 1
in subtle ways. First IsInt( Z(p)^0 )
(see IsInt)
is false
and IsFFE( Z(p)^0 )
(see IsFFE) is true
, whereas it
is just the other way around for the integer 1. Also 1+1
is 2
,
whereas, e.g., Z(2)^0 + Z(2)^0
is 0*Z(2)
.
The various roots returned by Z
for finite fields of the same
characteristic are compatible in the following sense. If the field
GF(pn) is a subfield of the field GF(pm), i.e., n divides m,
then Z(pn) = Z(pm)(pm-1)/(pn-1). Note that this is the simplest
relation that may hold between a generator of GF(pn) and GF(pm),
since Z(pn) is an element of order pm-1 and Z(pm) is an element
of order pn-1. This is achieved by choosing Z(p) as the smallest
primitive root modulo p and Z(pn) as a root of the n-th Conway
polynomial of characteristic p. Those polynomials where defined by
J.H. Conway and computed by R.A. Parker.
gap> z := Z(16); Z(2^4) gap> z*z; Z(2^4)^2
18.2 Comparisons of Finite Field Elements
z1 = z2
z1 <> z2
The equality operator =
evaluates to true
if the two elements in a
finite field z1 and z2 are equal and to false
otherwise. The
inequality operator <>
evaluates to true
if the two elements in a
finite finite field z1 and z2 are not equal and to false
otherwise.
Note that the integer 0 is not equal to the zero element in any finite
field. There comparisons z = 0
will always evaluate to false
. Use
z = 0*z
instead, or even better z = F.zero
, where F is the
field record for a finite field of the same characteristic.
gap> Z(2^4)^10 = Z(2^4)^25; true #Z(2^4)
has order 15 gap> Z(2^4)^10 = Z(2^2)^2; true # shows the embedding ofGF(4)
intoGF(16)
gap> Z(2^4)^10 = Z(3); false
z1 < z2
z1 <= z2
z1 > z2
z1 >= z2
The operators <
, <=
, >
, and =>
evaluate to true
if the
element in a finite field z1 is less than, less than or equal to,
greater than, and greater than or equal to the element in a finite field
z2.
Elements in finite fields are ordered as follows. If the two elements lie in fields of different characteristics the one that lies in the field with the smaller characteristic is smaller. If the two elements lie in different fields of the same characteristic the one that lies in the smaller field is smaller. If the two elements lie in the same field and one is the zero and the other is not, the zero element is smaller. If the two elements lie in the same field and both are nonzero, and are represented as Z(pd)i1 and Z(pd)i2 respectively, then the one with the smaller i is smaller.
You can compare elements in a finite field with objects of other types. Integers, rationals, and cyclotomics are smaller than elements in finite fields, all other objects are larger. Note especially that the integer 0 is smaller than the zero in every finite field.
gap> Z(2) < Z(3); true gap> Z(2) < Z(4); true gap> 0*Z(2) < Z(2); true gap> Z(4) < Z(4)^2; true gap> 0 < 0*Z(2); true gap> Z(4) < [ Z(4) ]; true
18.3 Operations for Finite Field Elements
z1 + z2
z1 - z2
z1 * z2
z1 / z2
The operators +
, -
, *
and /
evaluate to the sum, difference,
product, and quotient of the two finite field elements z1 and z2,
which must lie in fields of the same characteristic. For the quotient
/
z2 must of course be nonzero. The result must of course lie in a
finite field of size less than or equal to 216, otherwise an error
is signalled.
Either operand may also be an integer i. If i is zero it is taken as
the zero in the finite field, i.e., F.zero
, where F is a field
record for the finite field in which the other operand lies. If i is
positive, it is taken as i-fold sum F.one+F.one+..+F.one
. If
i is negative it is taken as the additive inverse of -i
.
gap> Z(8) + Z(8)^4; Z(2^3)^2 gap> Z(8) - 1; Z(2^3)^3 gap> Z(8) * Z(8)^6; Z(2)^0 gap> Z(8) / Z(8)^6; Z(2^3)^2 gap> -Z(9); Z(3^2)^5
z ^ i
The powering operator ^
returns the i-th power of the element in a
finite field z. i must be an integer. If the exponent i is zero,
z^i
is defined as the one in the finite field, even if z is
zero; if i is positive, z^i
is defined as the i-fold product
z*z*..*z
; finally, if i is negative, z^i
is defined
as (1/z)^-i
. In this case z must of course be nonzero.
gap> Z(4)^2; Z(2^2)^2 gap> Z(4)^3; Z(2)^0 # is in fact 1 gap> (0*Z(4))^0; Z(2)^0
IsFFE( obj )
IsFFE
returns true
if obj, which may be an object of an arbitrary
type, is an element in a finite field and false
otherwise. Will signal
an error if obj is an unbound variable.
Note that integers, even though they can be multiplied with elements in
finite fields, are not considered themselves elements in finite fields.
Therefore IsFFE
will return false
for integer arguments.
gap> IsFFE( Z(2^4)^7 ); true gap> IsFFE( 5 ); false
CharFFE( z )
or CharFFE( vec )
or CharFFE( mat )
CharFFE
returns the characteristic of the finite field F containing
the element z, respectively all elements of the vector vec over a
finite field (see Vectors), or matrix mat over a finite field (see
Matrices).
gap> CharFFE( Z(16)^7 ); 2 gap> CharFFE( Z(16)^5 ); 2 gap> CharFFE( [ Z(3), Z(27)^11, Z(9)^3 ] ); 3 gap> CharFFE( [ [ Z(5), Z(125)^3 ], [ Z(625)^13, Z(5) ] ] ); Error, CharFFE: <z> must be a finite field element, vector, or matrix # The smallest finite field which contains all four of these elements # is too large for GAP3
DegreeFFE( z )
or DegreeFFE( vec )
or DegreeFFE( mat )
DegreeFFE
returns the degree of the smallest finite field F
containing the element z, respectively all elements of the vector vec
over a finite field (see Vectors), or matrix mat over a finite field
(see Matrices). For vectors and matrices, an error is signalled if the
smallest finite field containing all elements of the vector or matrix has
size larger than 216.
gap> DegreeFFE( Z(16)^7 ); 4 gap> DegreeFFE( Z(16)^5 ); 2 gap> DegreeFFE( [ Z(3), Z(27)^11, Z(9)^3 ] ); 6 gap> DegreeFFE( [ [ Z(5), Z(125)^3 ], [ Z(625)^13, Z(5) ] ] ); Error, DegreeFFE: <z> must be a finite field element, vector, or matrix # The smallest finite field which contains all four of these elements # is too large for GAP3
OrderFFE( z )
OrderFFE
returns the order of the element z in a finite field. The
order is the smallest positive integer i such that z^i
is 1.
The order of the zero in a finite field is defined to be 0.
gap> OrderFFE( Z(16)^7 ); 15 gap> OrderFFE( Z(16)^5 ); 3 gap> OrderFFE( Z(27)^11 ); 26 gap> OrderFFE( Z(625)^13 ); 48 gap> OrderFFE( Z(211)^0 ); 1
IntFFE( z )
IntFFE
returns the integer corresponding to the element z, which must
lie in a finite prime field. That is IntFFE
returns the smallest
nonnegative integer i such that i * z^ 0 = z
.
The correspondence between elements from a finite prime field of
characteristic p and the integers between 0 and p-1
is defined by
choosing Z(p)
the smallest primitive root mod p (see
PrimitiveRootMod).
gap> IntFFE( Z(13) ); 2 gap> PrimitiveRootMod( 13 ); 2 gap> IntFFE( Z(409) ); 21 gap> IntFFE( Z(409)^116 ); 311 gap> 21^116 mod 409; 311
LogFFE( z )
LogFFE( z, r )
In the first form LogFFE
returns the discrete logarithm of the element
z in a finite field with respect to the root FieldFFE(z).root
. An
error is signalled if z is zero.
In the second form LogFFE
returns the discrete logarithm of the element
z in a finite field with respect to the root r. An error is
signalled if z is zero, or if z is not a power of r.
The discrete logarithm of an element z with respect to a root r is the smallest nonnegative integer i such that ri = z.
gap> LogFFE( Z(409)^116 ); 116 gap> LogFFE( Z(409)^116, Z(409)^2 ); 58
GaloisField( p^d )
GF( p^d )
GaloisField( p\|S, d\|pol\|bas )
GF( p\|S, d\|pol\|bas )
GaloisField
returns a field record (see Field Records) for a finite
field. It takes two arguments. The form GaloisField(p,d)
, where
p,d are integers, can also be given as GaloisField(p^d)
. GF
is an abbreviation for GaloisField
.
The first argument specifies the subfield S over which the new field F is to be taken. It can be a prime or a finite field record. If it is a prime p, the subfield is the prime field of this characteristic. If it is a field record S, the subfield is the field described by this record.
The second argument specifies the extension. It can be an integer, an irreducible polynomial, or a base. If it is an integer d, the new field is constructed as the polynomial extension with the Conway polynomial of degree d over the subfield S. If it is an irreducible polynomial pol, in which case the elements of the list pol must all lie in the subfield S, the new field is constructed as polynomial extension of the subfield S with this polynomial. If it is a base bas, in which case the elements of the list bas must be linear independently over the subfield S, the new field is constructed as a linear vector space over the subfield S.
Note that the subfield over which a field was constructed determines over which field the Galois group, conjugates, norm, trace, minimal polynom, and characteristic polynom are computed (see GaloisGroup, Conjugates, Norm, Trace, MinPol, CharPol, and Field Functions for Finite Fields).
gap> GF( 2^4 ); GF(2^4) gap> GF( GF(2^4), 2 ); GF(2^8)/GF(2^4)
FrobeniusAutomorphism( F )
FrobeniusAutomorphism
returns the Frobenius automorphism of the finite
field F as a field homomorphism (see Field Homomorphisms).
The Frobenius automorphism f of a finite field F of characteristic p is the function that takes each element z of F to its p-th power. Each automorphism of F is a power of the Frobenius automorphism. Thus the Frobenius automorphism is a generator for the Galois group of F (and an appropriate power of it is a generator of the Galois group of F over a subfield S) (see GaloisGroup).
gap> f := GF(16); GF(2^4) gap> x := FrobeniusAutomorphism( f ); FrobeniusAutomorphism( GF(2^4) ) gap> Z(16) ^ x; Z(2^4)^2
The image of an element z under the i-th power of the Frobenius
automorphism f of a finite field F of characteristic p is simply
computed by computing the p^i
-th power of z. The product of the
i-th power and the j-th power of f is the k-th power of f,
where k is i*j mod (Size(F)-1)
. The zeroth power of f is
printed as IdentityMapping( F )
.
18.12 Set Functions for Finite Fields
Finite fields are of course domains. Thus all set theoretic functions are applicable to finite fields (see chapter Domains). This section gives further comments on the definitions and implementations of those functions for finite fields. All set theoretic functions not mentioned here are not treated specially for finite fields.
Elements
The elements of a finite field are computed using the fact that the finite field is a vector space over its prime field.
in
The membership test is of course very simple, we just have to test
whether the element is a finite field element with IsFFE
, whether it
has the correct characteristic with CharFFE
, and whether its degree
divides the degree of the finite field with DegreeFFE
(see IsFFE,
CharFFE, and DegreeFFE).
Random
A random element of GF(pn) is computed by computing a random integer i from [0..pn-1] and returning 0*Z(p) if i = 0 and Z(pn)i-1 otherwise.
Intersection
The intersection of GF(pn) and GF(pm) is the finite field GF(pGcd(n,m)), and is returned as finite field record.
18.13 Field Functions for Finite Fields
Finite fields are, as the name already implies, fields. Thus all field functions are applicable to finite fields and their elements (see chapter Fields). This section gives further comments on the definitions and implementations of those functions for finite fields. All domain functions not mentioned here are not treated specially for finite fields.
Field
and DefaultField
Both Field
and DefaultField
return the smallest finite field
containing the arguments as an extension of the prime field.
GaloisGroup
The Galois group of a finite field F of size pm over a subfield S of size q = pn is a cyclic group of size m/n. It is generated by the Frobenius automorphism that takes every element of F to its q-th power. This automorphism of F leaves exactly the subfield S fixed.
Conjugates
According to the above theorem about the Galois group, each element of F has m/n conjugates, z, zq, zq2, ..., zqm/n-1.
Norm
The norm is the product of the conjugates, i.e., z{pm-1/pn-1}. Because we have Z(pn) = Z(pm){pm-1/pn-1}, it follows that Norm( GF(pm)/GF(pn), Z(pm)i ) = Z(pn)i.
gap3-jm