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.
‣ 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
‣ 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
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.
‣ 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
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).
‣ 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
‣ 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 ]
‣ 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])
‣ 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])
‣ 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
generated by GAPDoc2HTML