# 18 Finite Fields

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"`.

## 18.1 Finite Field Elements

`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 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(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 ```

## 18.4 IsFFE

`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 ```

## 18.5 CharFFE

`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 ```

## 18.6 DegreeFFE

`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 ```

## 18.7 OrderFFE

`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 ```

## 18.8 IntFFE

`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 ```

## 18.9 LogFFE

`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 ```

## 18.10 GaloisField

`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) ```

## 18.11 FrobeniusAutomorphism

`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
24 Jun 2022