4 Utilities from the **StandardFF** package

`‣ StandardAffineShift` ( q, i ) | ( function ) |

Returns: an integer in range `[0..q-1]`

This function returns (m `i` + a) mod `q`, where m is the largest integer prime to `q` and ≤ 4 `q` / 5, and a is the largest integer ≤ 2 `q` / 3.

For fixed q this function provides a bijection on the range `[0..q-1]`

.

gap> List([0..10], i-> StandardAffineShift(11, i)); [ 7, 4, 1, 9, 6, 3, 0, 8, 5, 2, 10 ]

`‣ FindLinearCombination` ( v, start ) | ( function ) |

Returns: a pair `[serec, lk]`

of a record and vector or `fail`

Repeated calls of this function build up a semiechelon basis from the given arguments `v` which must be row vectors. To initialize a computation the function is called with a start vector `v` and `false`

as second argument. The return value is a pair `[serec, lk]`

where `serec`

is a record which collects data from the previous calls of the function and `lk`

is a row vector which expresses `v` as linear combination of the vectors from previous calls, or `fail`

if there is no such linear combination. In the latter case the data in the record is extended with the linearly independent vector `v`

.

In the following example we show how to compute a divisor of the minimal polynomial of a matrix.

gap> mat := Product(GeneratorsOfGroup(Sp(30,5)));; gap> x := Indeterminate(GF(5), "x");; gap> v := (mat^0)[1];; gap> b := FindLinearCombination(v, false);; gap> repeat > v := v*mat; > l := FindLinearCombination(v, b[1]); > until IsList(l[2]); gap> mp := Value(UnivariatePolynomial(GF(5), > Concatenation(-l[2], [One(GF(5))])), x); x^30+Z(5)^3*x^29+Z(5)^3*x+Z(5)^0 gap> # equal to minimal polynomial because of degree gap> mp = Value(MinimalPolynomial(GF(5), mat), x); true

`‣ IsIrreducibleCoeffList` ( coeffs, q ) | ( function ) |

Returns: `true`

or `false`

The argument `coeffs` must be a list of elements in a finite field with `q` elements (or some subfield of it).

The function checks if the univariate polynomial f with coefficient list `coeffs` (ending with the leading coefficient) is irreducible over the field with `q` elements.

The algorithm computes the greatest common divisor of f with X^{q^i} - X for i = 1, 2, ... up to half of the degree of f.

gap> cs := Z(3)^0 * ConwayPol(3,8); [ Z(3), Z(3), Z(3), 0*Z(3), Z(3)^0, Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] gap> IsIrreducibleCoeffList(cs, 3); true gap> F := FF(17,4);; x := PrimitiveElement(F);; gap> cs := [x, x+x^0, 0*x, x^0]; [ ZZ(17,4,[0,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ] gap> while not IsIrreducibleCoeffList(cs, 17^4) do > cs[1] := cs[1] + One(F); > od; gap> cs; [ ZZ(17,4,[8,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ]

`‣ FindConjugateZeroes` ( K, cpol, qq ) | ( function ) |

Returns: a list of field elements

The arguments must be a finite field `K`, a polynomial `cpol` over `K` (or its coefficient list) and the order `qq` of a subfield of `K`. The polynomial must have coeffcients in the subfield with `qq` elements, must be irreducible over this subfield and split into linear factors over `K`. The function `FindConjugateZeroes`

returns the list of zeroes of `cpol` in `K`.

gap> K := GF(67,18); GF(67^18) gap> F := FF(67,18); FF(67, 18) gap> p1 := DefiningPolynomial(K);; gap> p2 := DefiningPolynomial(F);; gap> lK := FindConjugateZeroes(K, p2, 67);; gap> lF := FindConjugateZeroes(F, p1, 67);; gap> Minimum(List(lF, SteinitzNumber)); 12274789318154414216760893584069

`‣ ZeroesConway` ( F ) | ( function ) |

Returns: a list of field elements

Here, `F` must be a standard finite field, say of degree n over the prime field with p elements. This function returns the same as `FindConjugateZeroes(F, One(F)*ConwayPol(p, n), p)`

(using a specific implementation).

gap> F := FF(23,29); FF(23, 29) gap> l := Set(FindConjugateZeroes(F, One(F)*ConwayPol(23,29), 23));; gap> l = Set(ZeroesConway(F)); true

`‣ SteinitzPairConwayGenerator` ( F ) | ( function ) |

Returns: a pair of integers

For a standard finite field `F` of order q for which a Conway polynomial (see `ConwayPolynomial`

(Reference: ConwayPolynomial)) is known this function returns the `SteinitzPair`

(2.4-1) for the element of `F` corresponding to `Z(q)`

(which is by definition the zero of the Conway polynomial in `F` with the smallest Steinitz number which is compatible with the choice in all proper subfields).

This is used to construct the `StandardIsomorphismGF`

(2.4-5) for `F`.

gap> F := FF(23,18); FF(23, 18) gap> st := SteinitzPairConwayGenerator(F); [ 18, 1362020736983803830549380 ] gap> st9 := SteinitzPairConwayGenerator(FF(23,9)); [ 9, 206098743447 ] gap> st6 := SteinitzPairConwayGenerator(FF(23,6)); [ 6, 45400540 ] gap> z := ElementSteinitzNumber(F, st[2]);; gap> z9 := ElementSteinitzNumber(F, SteinitzNumber(F, st9));; gap> z6 := ElementSteinitzNumber(F, SteinitzNumber(F, st6));; gap> e9 := (Size(F)-1)/(23^9-1); 1801152661464 gap> e6 := (Size(F)-1)/(23^6-1); 21914624580056211 gap> z9 = z^e9; true gap> z6 = z^e6; true gap> l := Filtered(ZeroesConway(F), x-> x^e9 = z9 and x^e6 = z6);; gap> List(l, SteinitzNumber); [ 1362020736983803830549380 ]

`‣ DLog` ( base, x[, m] ) | ( function ) |

Returns: an integer

The argument `base` must be a multiplicative element and `x` must lie in the cyclic group generated by `base`. The third argument `m` must be the order of `base` or its factorization. If `m` is not given, it is computed first. This function returns the discrete logarithm, that is an integer e such that `base`^e = `x`.

If `m` is prime then Shanks' algorithm is used (which needs O(sqrt`m`) space and time). Otherwise let `m` = r l and e = a + b r with 0 ≤ a < r. Then a = `DLog`

(`base`^l, `x`^l, r) and b = `DLog`

(`base`^r, `x`/`base`^a, l).

This function is used for a method of `LogFFE`

(Reference: LogFFE).

gap> F := FF(67, 12); FF(67, 12) gap> st := SteinitzPairConwayGenerator(F); [ 12, 5118698034368952035290 ] gap> z := ElementSteinitzNumber(F, st[2]);; gap> x := StandardPrimitiveRoot(F);; gap> DLog(z, x, Size(F)-1); 231901568073107448223 gap> K := GF(67,12); GF(67^12) gap> zz := Z(67^12); z gap> LogFFE(zz^2+1, zz); 1667375214152688471247

`‣ InvModCoeffs` ( fcoeffs, gcoeffs ) | ( operation ) |

Returns: a list of `fail`

The arguments `fcoeffs` and `gcoeffs` are coeffient lists of two polynomials f and g. This operation returns the coefficient list of the inverse f^-1 modulo g, if f and g are coprime, and `fail`

otherwise.

The default method computes the inverse by the extended Euclidean algorithm.

gap> f := Z(13)^0*[ 1, 10, 1, 11, 0, 1 ];; gap> g := Z(13)^0*[ 5, 12, 5, 12, 2, 0, 2 ];; gap> InvModCoeffs(f, g); fail gap> GcdCoeffs(f, g); [ Z(13)^0, 0*Z(13), Z(13)^0 ] gap> f[1]:=f[1]+1;; gap> finv := InvModCoeffs(f, g); [ Z(13)^9, Z(13)^10, Z(13)^10, Z(13)^8, Z(13)^5, Z(13)^6 ] gap> pr := ProductCoeffs(finv, f);; gap> ReduceCoeffs(pr, g);; ShrinkRowVector(pr);; pr; [ Z(13)^0 ]

`‣ BerlekampMassey` ( u ) | ( function ) |

Returns: a list of field elements

The argument `u` is a list of elements in a field F. This function implements the Berlekamp-Massey algorithm which returns the shortest sequence c of elements in F such that for each i > l, the length of c, we have u[i] = ∑_{j=1}^l `u`[i-j] c[j].

gap> x := Indeterminate(GF(23), "x");; gap> f := x^5 + Z(23)^16*x + Z(23)^12;; gap> u := List([1..50], i-> Value(x^i mod f, 0));; gap> c := BerlekampMassey(u);; gap> ForAll([6..50], i-> u[i] = Sum([1..5], j-> u[i-j]*c[j])); true gap> -c; [ 0*Z(23), 0*Z(23), 0*Z(23), Z(23)^16, Z(23)^12 ]

`‣ MinimalPolynomialByBerlekampMassey` ( x ) | ( function ) |

`‣ MinimalPolynomialByBerlekampMasseyShoup` ( x ) | ( function ) |

Returns: the minimal polynomial of `x`

Here x must be an element of an algebraic extension field F/K. (K must be the `LeftActingDomain`

(Reference: LeftActingDomain) of F). This function computes the minimal polynomial of `x` over K by applying the Berlekamp-Massey algorithm to the list of traces of `x`^i.

The second variant uses the algorithm by Shoup in [Sho99].

gap> x := Indeterminate(GF(23), "x");; gap> f := x^5 + Z(23)^16*x + Z(23)^12;; gap> F := AlgebraicExtension(GF(23), f);; gap> mp := MinimalPolynomialByBerlekampMassey(PrimitiveElement(F));; gap> Value(mp, x) = f; true gap> mp = MinimalPolynomialByBerlekampMasseyShoup(PrimitiveElement(F)); true

Let G be a finite group, g ∈ G, and ρ: G -> GL(d,p^n)be a representation over a finite field. The Brauer character value χ(g) of ρ at g is defined as the sum of the eigenvalues of ρ(g) in the algebraic closure of F_p lifted to complex roots of unity.

The lift used by `BrauerCharacterValue`

(Reference: BrauerCharacterValue) and in the computation of many Brauer character tables (available through the **CTblLib** package) is defined by Conway polynomials (see `ConwayPolynomial`

(Reference: ConwayPolynomial)): They define the primitive root `Z(q)`

in `GF(q)`

which is mapped to exp(2 π i / (q-1)) (that is `E(q-1)`

in **GAP**).

Another lift is defined by the function `StandardCyclicGenerator`

(3.1-1) provided by this package. Here, `StandardCyclicGenerator(F, m)`

is mapped to exp(2 π i / m) (that is `E(m)`

in **GAP**).

The following function translates between these two lifts.

`‣ StandardValuesBrauerCharacter` ( tab, bch ) | ( function ) |

Returns: a Brauer character

`‣ IsGaloisInvariant` ( tab, bch ) | ( function ) |

Returns: `true`

or `false`

The argument `tab` must be a Brauer character table for which the Brauer characters are defined with respect to the lift given by Conway polynomials. And `bch` must be an irreducible Brauer character of this table.

The function `StandardValuesBrauerCharacter`

recomputes the values corresponding to the lift given by `StandardCyclicGenerator`

(3.1-1), provided that the Conway polynomials for computing the Frobenius character values of `bch` are available. If Conway polynomials are missing the corresponding character values are substituted by `fail`

. If the result does not contain `fail`

it is a class function which is Galois conjugate to `bch` (see `GaloisCyc`

(Reference: GaloisCyc for a class function)).

The utility `IsGaloisInvariant`

returns `true`

if all Galois conjugates of `bch` are Brauer characters in `tab`. If this is the case then different lifts will permute the Galois conjugates and all of them are Brauer characters with respect to any lift.

WARNING: The result of this function may not be a valid Brauer character for the table `tab` (that is an integer linear combination of irreducible Brauer characters in `tab`). For a proper handling of several lifts the data structure of Brauer character tables needs to be extended (it must refer to the lift), and then the result of this function should return a Brauer character of another table that refers to another lift.

gap> tab := BrauerTable("M", 19); BrauerTable( "M", 19 ) gap> # cannot translate some values to different lift gap> fail in AsList(StandardValuesBrauerCharacter(tab, Irr(tab)[16])); true gap> # but table contains the irreducible Brauer characters for any lift gap> ForAll(Irr(tab), bch-> IsGaloisInvariant(tab, bch)); true gap> tab := BrauerTable("A18", 3); BrauerTable( "A18", 3 ) gap> # here different lifts lead to different Brauer character tables gap> bch := Irr(tab)[38];; gap> IsGaloisInvariant(tab, bch); false gap> new := StandardValuesBrauerCharacter(tab, bch);; gap> fail in AsList(new); false gap> Position(Irr(tab), new); fail

The inverse of a lift is used to reduce character values in characteristic 0 modulo a prime p. Choosing a lift is equivalent to choosing a p-modular system. **GAP** has the function `FrobeniusCharacterValue`

(Reference: FrobeniusCharacterValue) which computes this reduction with respect to the lift defined by Conway polynomials.

Here is the corresponding function with respect to the lift constructed in this package.

`‣ SmallestDegreeFrobeniusCharacterValue` ( cyc, p ) | ( function ) |

Returns: a positive integer or `fail`

`‣ StandardFrobeniusCharacterValue` ( cyc, F ) | ( function ) |

Returns: an element of `F` or `fail`

The argument `cyc` must be a cyclotomic whose conductor and denominator are not divisible by the prime integer `p` or the characteristic of the standard finite field `F`.

The order of the multiplicative group of `F` must be divisible by the conductor of `cyc`.

Then `StandardFrobeniusCharacterValue`

returns the image of `cyc` in `F` under the homomorphism which maps the root of unity `E(n)`

to the `StandardCyclicGenerator`

(3.1-1) of order `n`

in `F`. If the conditions are not fulfilled the function returns `fail`

.

The function `SmallestDegreeFrobeniusCharacterValue`

returns the smallest degree of a field over the prime field of order `p` containing the image of `cyc`.

gap> SmallestDegreeFrobeniusCharacterValue(E(13), 19); 12 gap> F := FF(19,12); FF(19, 12) gap> x := StandardFrobeniusCharacterValue(E(13),F);; gap> x^13; ZZ(19,12,[1]) gap> x = StandardCyclicGenerator(F, 13); true gap> cc := (E(13)+1/3)^4;; gap> xx := StandardFrobeniusCharacterValue(cc, F);; gap> xx = StandardFrobeniusCharacterValue(E(13)+1/3, F)^4; true

`‣ CANFACT` | ( global variable ) |

This variable contains a list where for each prime p < 10000 the entry `CANFACT[p]`

holds a list of integers i such that the number p^i-1 (the order of the multiplicative group of the finite field `FF(p,i)`

) can be factored by **GAP** in a short time. This is based on the enormous efforts to find factors of numbers of this form, see [Cro].

For p < 10 the range of considered exponents is 2 ≤ i ≤ 2000, for 10 < p < 100 it is 2 ≤ i ≤ 500, and for 100 < p < 10000 it is 2 ≤ i ≤ 100.

These data describe (in May 2022) 112968 pairs `p, i`

such that `StandardPrimitiveRoot(FF(p,i))`

can be computed in reasonable time. Only for 10858 of these cases **GAP** knows or can easily compute the corresponding Conway polynomial (see `ConwayPolynomial`

(Reference: ConwayPolynomial)).

The current content of `CANFACT`

was generated after updating the data in the **FactInt** package concerning factors of numbers of the form a^n ± 1. If you want to use that list you should also update your **GAP** installation with:

FetchMoreFactors( "https://maths-people.anu.edu.au/~brent/ftp/factors/factors.gz", false); FetchMoreFactors( "http://myfactorcollection.mooo.com:8090/brentdata/May31_2022/factors.gz", true);

`‣ AllPrimeDegreePolynomials` ( p, bound ) | ( function ) |

`‣ AllFF` ( p, bound ) | ( function ) |

`‣ AllPrimitiveRoots` ( p, bound ) | ( function ) |

`‣ AllPrimitiveRootsCANFACT` ( ) | ( function ) |

`‣ AllFieldsWithConwayPolynomial` ( ["ConwayGen"][,] ["MiPo"] ) | ( function ) |

These function compute all fields in some range, sometimes with further data. All functions return a list with some timings and print a log-file in the current directory.

`AllPrimeDegreePolynomials`

computes all irreducible polynomials of prime degree needed for the construction of all finite fields of order `p`^i, 1 ≤ i ≤ `bound`. This is the most time consuming part in the construction of the fields.

`AllFF`

computes all `FF(p,i)`

for 1 ≤ i ≤ `bound`. When the previous function was called before for the same range, this function spends most of its time by computing the minimal polynomials of the standardized primitive elements of `FF(p,i)`

.

`AllPrimitiveRoots`

computes the standardized primitive roots in `FF(p,i)`

for 1 ≤ i ≤ `bound`. The most time consuming cases are when a large prime divisor r of p^i-1 already divides p^j-1 for some j < i (but then r divides i/j). Cases where **GAP** cannot factorize p^i-1 (that is i is not contained in `CANFACT[p]`

) are skipped.

`AllPrimitiveRootsCANFACT`

does the same as the previous function for all pairs p, i stored in `CANFACT`

(4.8-1).

`AllFieldsWithConwayPolynomial`

computes all `FF(p,i)`

for the cases where **GAP** knows the precomputed `ConwayPolynomial(p,i)`

. With the optional argument `"ConwayGen`

the function computes for all fields the `SteinitzPairConwayGenerator`

(4.4-3) and writes it into a file `SteinitzPairConway`

. With the optional argument `"MiPo"`

the function also computes the minimal polynomials of the `StandardPrimitiveRoot`

(3.1-1) and writes it to a file `MiPoPrimitiveRoots`

(these polynomials have the same compatibility properties as Conway polynomials).

We mention some features of this package which may be temporary, vanish or changed.

A directory `ntl`

contains some simple standalone programs which use the library NTL [Sho]. There is a function `StandardIrreducibleCoeffListNTL(K, d, a)`

which can be used instead of `StandardIrreducibleCoeffListNTL(K, d, a)`

when `K`

is a prime field. This gives a good speedup for not too small `d`

, say `d`

>500.

generated by GAPDoc2HTML