GAP (StandardFF) - Chapter 2: Standard finite fields

In [Lüb23] we define for each prime p and positive integer n a standardized model for the finite field with p^n elements. This is done by defining for each prime r polynomials of degree r which define recursively r-power extensions of the prime field GF(p) and by combining these for all r | n in a unique tower of extensions of finite fields where the successive degrees are non-decreasing primes.

Relative to this tower of prime degree extensions the resulting field comes with a natural basis over the prime field which we call the tower basis. This construction has the nice property that whenever n | m then the tower basis of the field with p^n elements is a subset of the tower basis of the field with p^m elements. (See [Lüb23] for more details.)

Expressing elements as linear combination of the tower basis we define a bijection from the elements in the field of order p^n to the range [0..p^n-1]; we call the number assigned to an element its Steinitz number.

Via this construction each element in the algebraic closure of GF(p) can be identified by its degree d over the prime field and its Steinitz number in the field with p^d elements (we call this a Steinitz pair).

Since arithmetic in simple algebraic extensions is more efficient than in iterated extensions we construct the fields recursively as simple extensions, and including information about the base change between the tower basis and the basis given by the powers of the generator.

2.2 Creating standard finite fields

2.2-1 Constructing standard finite fields

The arguments are a prime p and a positive integer n. The function FF (or its synomym StandardFiniteField) is one of the main functions of this package. It returns a standardized field F of order p^n. It is implemented as a simple extension over the prime field GF(p) using AlgebraicExtension (Reference: AlgebraicExtension)

The polynomials used for the prime degree extensions are accessible with StandardPrimeDegreePolynomial. For arguments p, r, k it returns the irreducible polynomial of degree r for the k-th iterated extension of degree r over the prime field. The polynomial is in the variable xr_k and the coefficients can contain variables xr_l with l < k.

gap> Fp := FF(2, 1);
GF(2)
gap> F := FF(2, 100);
FF(2, 100)
gap> Size(F);
1267650600228229401496703205376
gap> p := NextPrimeInt(10^50);
100000000000000000000000000000000000000000000000151
gap> K := FF(p, 60);
FF(100000000000000000000000000000000000000000000000151, 60)
gap> LogInt(Size(K), 10);
3000
gap> F := FF(13, 9*5);
FF(13, 45)
gap> StandardPrimeDegreePolynomial(13, 3, 1);
x3_1^3+Z(13)^7
gap> StandardPrimeDegreePolynomial(13, 3, 2);
x3_2^3-x3_1
gap> StandardPrimeDegreePolynomial(13, 5, 1);
x5_1^5+Z(13)^4*x5_1^2+Z(13)^4*x5_1-Z(13)^0

2.2-2 Filters for standard fields

These properties identify the finite fields constructed with FF (2.2-1). Prime fields constructed as FF(p, 1) have the property IsStandardPrimeField. They are identical with GF(p), but calling them via FF (2.2-1) we store some additional information in these objects.

The fields constructed by FF(p,k) with k > 1 have the property IsStandardFiniteField. Elements x in such a field are in IsStandardFiniteFieldElement.

gap> F := FF(19,1);
GF(19)
gap> IsStandardFiniteField(F);
false
gap> IsStandardPrimeField(F);
true
gap> F := FF(23,48);
FF(23, 48)
gap> IsStandardFiniteField(F);
true
gap> IsStandardFiniteFieldElement(Random(F));
true

2.3 Elements in standard finite fields

For fields in IsStandardFiniteField (2.2-2) we provide functions to map elements to their linear combination of the tower basis, to their Steinitz number and Steinitz pair, or to their representing multivariate polynomial with respect to all prime degree extensions, and vice versa.

2.3-1 Maps for elements of standard finite fields

Here, F is always a standard finite field (IsStandardFiniteField (2.2-2)) and a is an element of F.

AsVector returns the coefficient vector of a with respect to the tower basis of F. And vice versa ElementVector returns the element of F with the given coefficient vector.

Similarly, AsPolynomial returns the (reduced) polynomial in the indeterminates defining the tower of F. Here, for each prime r dividing the degree of the field the polynomial defining the k-th extension of degree r over the prime field is written in the variable xr_k. And ElementPolynomial returns the element of F represented by the given polynomial (which does not need to be reduced).

Finally, SteinitzNumber returns the Steinitz number of a. And ElementSteinitzNumber returns the element with given Steinitz number.

gap> F := FF(17, 12);
FF(17, 12)
gap> a := PrimitiveElement(F);; a := a^11-3*a^5+a;
ZZ(17,12,[0,1,0,0,0,14,0,0,0,0,0,1])
gap> v := AsVector(a);
< immutable compressed vector length 12 over GF(17) >
gap> a = ElementVector(F, v);
true
gap> ExtRepOfObj(a) = v * TowerBasis(F);
true
gap> pol := AsPolynomial(a);;
gap> ElementPolynomial(F, pol^10) = a^10;
true
gap> nr := SteinitzNumber(a);
506020624175737
gap> a = ElementSteinitzNumber(F, nr);
true
gap> ## primitive element of FF(17, 6)
gap> y := ElementSteinitzNumber(F, 17^5);
ZZ(17,12,[0,0,1,0,0,0,12,0,0,0,5,0])
gap> y = ValuePol([0,0,1,0,0,0,12,0,0,0,5,0], PrimitiveElement(F));
true
gap> x6 := Indeterminate(FF(17,1), "x6");;
gap> MinimalPolynomial(FF(17,1), y, x6) = DefiningPolynomial(FF(17,6));
true

2.4 Embeddings of standard finite fields

The tower basis of a standard finite field F contains the tower basis of any subfield. This yields a construction of canonical embeddings of all subfields of F into F. And one can easily read off the smallest subfield containing an element in F from its coefficient vector with respect to the tower basis. Each element of the algebraic closure of FF(p,1) is uniquely determined by its degree d and its Steinitz number in FF(p, d).

2.4-1 SteinitzPair

The argument a must be an element in IsStandardFiniteFieldElement (2.2-2). Then SteinitzPair returns a pair [d, nr] where d is the degree of a over the prime field FF(p, 1) and nr is the Steinitz number of a considered as element of FF(p, d).

In the second variant a standard finite field K is given and the Steinitz number of an element in K and the result is the Steinitz pair of the corresponding element.

The inverse map is provided by a method for SteinitzNumber which gets a standard finite field and a Steinitz pair.

gap> F := FF(7, 360);
FF(7, 360)
gap> t := ElementSteinitzNumber(F, 7^10);; # prim. elt of FF(7,12)
gap> sp := SteinitzPair(t);
[ 12, 117649 ]
gap> H := FF(7, 12);
FF(7, 12)
gap> b := ElementSteinitzNumber(H, 117649);
ZZ(7,12,[0,1,0,0,0,0,0,0,0,0,0,0])
gap> Value(MinimalPolynomial(FF(7,1), t), b);
ZZ(7,12,[0])
gap> nr := SteinitzNumber(t);
282475249
gap> nr = SteinitzNumber(F, sp);
true
gap> sp = SteinitzPair(F, nr);
true

2.4-2 Embedding

Let F and H be standard finite fields and H be isomorphic to a subfield of F. This function returns the canonical embedding of H into F.

gap> F := FF(7, 360);
FF(7, 360)
gap> H := FF(7, 45);
FF(7, 45)
gap> emb := Embedding(H, F);
MappingByFunction( FF(7, 45), FF(7, 360), function( x ) ... end )
gap> y := PrimitiveElement(H);
ZZ(7,45,[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
gap> x := y^emb;;
gap> ((y+One(H))^12345)^emb = (x+One(F))^12345;
true
gap> PreImageElm(emb, x^5);
ZZ(7,45,[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
gap> PreImageElm(emb, PrimitiveElement(F));
fail
gap> SteinitzNumber(y);
13841287201
gap> SteinitzNumber(x) mod 10^50;
72890819326613454654477690085519113574118965817601
gap> SteinitzPair(x);
[ 45, 13841287201 ]

2.4-3 ZZ

For a prime p, positive integer n and an integer list coeffs this function returns the element in FF(p, n) represented by the polynomial with coefficient list coeffs modulo p. Elements in standard finite fields are also printed in this way.

gap> x := ZZ(19,5,[1,2,3,4,5]);
ZZ(19,5,[1,2,3,4,5])
gap> a := PrimitiveElement(FF(19,5));
ZZ(19,5,[0,1,0,0,0])
gap> x = [1,2,3,4,5]*[a^0,a^1,a^2,a^3,a^4];
true
gap> One(FF(19,5)); # elements in prime field abbreviated
ZZ(19,5,[1])
gap> One(FF(19,5)) = ZZ(19,5,[1]);
true
gap> ZZ(19,5,Z(19^5)); # zero of ConwayPolynomial(19,5)
ZZ(19,5,[12,5,3,4,5])

2.4-4 MoveToSmallestStandardField

Here x and y must be elements in standard finite fields (of the same characteristic).

Then MoveToSmallestStandardField returns the element x as element of the smallest possible degree extension over the prime field.

The arithmetic operations are even possible when x and y are not represented as elements in the same field. In this case the elements are first mapped to the smallest field containing both.

gap> F := FF(1009,4);
FF(1009, 4)
gap> G := FF(1009,6);
FF(1009, 6)
gap> x := (PrimitiveElement(F)+One(F))^13;
ZZ(1009,4,[556,124,281,122])
gap> y := (PrimitiveElement(G)+One(G))^5;
ZZ(1009,6,[1,5,10,10,5,1])
gap> x+y;
ZZ(1009,12,[557,0,936,713,332,0,462,0,843,191,797,0])
gap> x-y;
ZZ(1009,12,[555,0,73,713,677,0,97,0,166,191,212,0])
gap> x*y;
ZZ(1009,12,[253,289,700,311,109,851,345,408,813,657,147,887])
gap> x/y;
ZZ(1009,12,[690,599,714,648,184,217,563,130,251,675,73,782])
gap> z  := -y + (x+y);
ZZ(1009,12,[556,0,0,713,0,0,784,0,0,191,0,0])
gap> SteinitzPair(z);
[ 4, 125450261067 ]
gap> x=z;
true
gap> MoveToSmallestStandardField(z);
ZZ(1009,4,[556,124,281,122])

2.4-5 StandardIsomorphismGF

The argument F must be a standard finite field, say FF(p,n) such that GAP can generate GF(p,n). This function returns the field isomorphism from GF(p,n) to F, which sends Z(p,n) to the element with Steinitz pair computed by SteinitzPairConwayGenerator (4.4-3).

gap> F := FF(13,21);
FF(13, 21)
gap> iso := StandardIsomorphismGF(F);
MappingByFunction( GF(13^21), FF(13, 21), function( x ) ... end )
gap> K := GF(13,21);
GF(13^21)
gap> x := Random(K);;
gap> l := [1,2,3,4,5];;
gap> ValuePol(l, x)^iso = ValuePol(l, x^iso);
true
gap> y :=  ElementSteinitzNumber(F, SteinitzPairConwayGenerator(F)[2]);;
gap> PreImageElm(iso, y);
z

2 Standard finite fields

2.1 Definition of standard finite fields