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. **GAP** supports finite fields of
size at most *2^{16}*.

The first section in this chapter describes how you can enter elements of
finite fields and how **GAP** prints them (see Finite Field Elements).

The next sections describe the operations applicable to finite field 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 Set Functions for Finite Fields).

Finite fields are of course fields, thus all field functions are Field Functions for Finite Fields).

All functions are in `LIBNAME/"finfield.g"`

.

- Finite Field Elements
- Comparisons of Finite Field Elements
- Operations for Finite Field Elements
- IsFFE
- CharFFE
- DegreeFFE
- OrderFFE
- IntFFE
- LogFFE
- GaloisField
- FrobeniusAutomorphism
- Set Functions for Finite Fields
- Field Functions for Finite Fields

`Z( `

`p`^`d` )

The function `Z`

returns the designated generator of the multiplicative
group of the finite field with

elements. `p`^`d``p` must be a prime
and

must be less than or equal to `p`^`d`*2^{16} = 65536*.

The root returned by `Z`

is a generator of the multiplicative group of
the finite field with *p^d* elements, which is cyclic. The order of the
element is of course *p^d-1*. The *p^d-1* different powers of the root
are exactly the nonzero elements of the finite field.

Thus all nonzero elements of the finite field with

elements
can be entered as `p`^`d``Z(`

. Note that this is also the form
that `p`^`d`)^`i`**GAP** uses to output those elements.

The additive neutral element is `0*Z(`

. It is different from the
integer `p`)`0`

in subtle ways. First `IsInt( 0*Z(`

(see IsInt) is
`p`) )`false`

and `IsFFE( 0*Z(`

(see IsFFE) is `p`) )`true`

, whereas it is
just the other way around for the integer 0.

The multiplicative neutral element is `Z(`

. It is different from
the integer `p`)^0`1`

in subtle ways. First `IsInt( Z(`

(see IsInt)
is `p`)^0 )`false`

and `IsFFE( Z(`

(see IsFFE) is `p`)^0 )`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(p^n)* is a subfield of the field *GF(p^m)*, i.e., *n* divides *m*,
then *Z(p^n) = Z(p^m)^{(p^m-1)/(p^n-1)}*. Note that this is the simplest
relation that may hold between a generator of *GF(p^n)* and *GF(p^m)*,
since *Z(p^n)* is an element of order *p^m-1* and *Z(p^m)* is an element
of order *p^n-1*. This is achieved by choosing *Z(p)* as the smallest
primitive root modulo *p* and *Z(p^n)* 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

`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

will always evaluate to `z` = 0`false`

. Use

instead, or even better `z` = 0*`z`

, where `z` = `F`.zero`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 of 'GF(4)' into 'GF(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(p^d)^{i_1}* and *Z(p^d)^{i_2}* 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

`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 *2^{16}*, 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.,

, where `F`.zero`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

. If
`F`.one+`F`.one+..+`F`.one`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,

is defined as the one in the finite field, even if `z`^`i``z` is
zero; if `i` is positive,

is defined as the `z`^`i``i`-fold product

; finally, if `z`*`z`*..*`z``i` is negative,

is defined
as `z`^`i``(1/`

. In this case `z`)^-`i``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( `

or `z` )`CharFFE( `

or `vec` )`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 {\GAP}

`DegreeFFE( `

or `z` )`DegreeFFE( `

or `vec` )`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 *2^{16}*.

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 {\GAP}

`OrderFFE( `

`z` )

`OrderFFE`

returns the order of the element `z` in a finite field. The
order is the smallest positive integer `i` such that

is 1.
The order of the zero in a finite field is defined to be 0.
`z`^`i`

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

is defined by
choosing `p`-1`Z(`

the smallest primitive root mod `p`)`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(`

. An
error is signalled if `z`).root`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 *r^i = 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(`

, where
`p`,`d`)`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, 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

-th power of `p`^`i``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

. The zeroth power of `i`*`j` mod (Size(`F`)-1)`f` is
printed as `IdentityMapping( `

.
`F` )

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(p^n)* is computed by computing a random integer
*i* from *[0..p^n-1]* and returning *0*Z(p)* if *i = 0* and
*Z(p^n)^{i-1}* otherwise.

`Intersection`

The intersection of *GF(p^n)* and *GF(p^m)* is the finite field
*GF(p^{Gcd(n,m)})*, and is returned as finite field record.

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 *p^m* over a subfield *S*
of size *q = p^n* 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, z^q, z^{q^2}, ..., z^{q^{m/n-1}}*.

`Norm`

The norm is the product of the conjugates, i.e., *z^{{p^m-1}/{p^n-1}}*.
Because we have *Z(p^n) = Z(p^m)^{{p^m-1}/{p^n-1}}*, it follows that
*Norm( GF(p^m)/GF(p^n), Z(p^m)^i ) = Z(p^n)^i*.

GAP 3.4.4

April 1997