Goto Chapter: Top 1 2 3 4 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

2 Standard finite fields
 2.1 Definition of standard finite fields
 2.2 Creating standard finite fields
 2.3 Elements in standard finite fields
 2.4 Embeddings of standard finite fields

2 Standard finite fields

2.1 Definition of 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
‣ StandardFiniteField( p, n )( function )
‣ FF( p, n )( function )

Returns: a finite field

‣ StandardPrimeDegreePolynomial( p, r, k )( function )

Returns: a polynomial of degree r

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 \(\textit{p}^{\textit{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
‣ IsStandardPrimeField( F )( property )
‣ IsStandardFiniteField( F )( property )
‣ IsStandardFiniteFieldElement( x )( category )

Returns: true or false

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
‣ AsVector( a )( method )

Returns: a vector over prime field of F

‣ ElementVector( F, v )( method )

Returns: an element in F

‣ AsPolynomial( a )( method )

Returns: a polynomial in variables of the tower of F

‣ ElementPolynomial( F, pol )( method )

Returns: an element in F

‣ SteinitzNumber( a )( method )

Returns: an integer

‣ ElementSteinitzNumber( F, nr )( method )

Returns: an element in F

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 x\(r\)_\(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
‣ SteinitzPair( a )( operation )

Returns: a pair of integers

‣ SteinitzPair( K, snr )( method )

Returns: a pair of integers

‣ SteinitzNumber( K, pair )( method )

Returns: an integer

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
‣ Embedding( H, F )( method )

Returns: a field homomorphism

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
‣ ZZ( p, n, coeffs )( operation )
‣ ZZ( p, n, ffe )( operation )

Returns: an element in FF(p, n)

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.

For convenience the third argument ffe can be in `GF(p,n)` (see GF (Reference: GF for characteristic and degree) and IsFFE (Reference: IsFFE)). This returns the image of ffe under the StandardIsomorphismGF (2.4-5) of FF(p,n).

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
‣ MoveToSmallestStandardField( x )( function )
‣ \+( x, y )( method )
‣ \*( x, y )( method )
‣ \-( x, y )( method )
‣ \/( x, y )( method )

Returns: a field element

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
‣ StandardIsomorphismGF( F )( function )

Returns: a field isomorphism

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
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 Bib Ind

generated by GAPDoc2HTML