‣ StandardAffineShift( q, i ) | ( function ) |
Returns: an integer in range [0..q-1]
This function returns \((m \textit{i} + a) \textrm{ mod } \textit{q}\), where \(m\) is the largest integer prime to q and \(\leq 4 \textit{q} / 5\), and a is the largest integer \(\leq 2 \textit{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, \ldots\) 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{\textit{m}})\) space and time). Otherwise let m \( = r l\) and \(e = a + b r\) with \(0 \leq a < r\). Then \(a =\) DLog\((\textit{base}^l, \textit{x}^l, r)\) and \(b = \) DLog\((\textit{base}^r, \textit{x}/\textit{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] = \sum_{{j=1}}^l \textit{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 \(\textit{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 \in G\), and \(\rho: G \to GL(d,p^n)\)be a representation over a finite field. The Brauer character value \(\chi(g)\) of \(\rho\) at \(g\) is defined as the sum of the eigenvalues of \(\rho(g)\) in the algebraic closure of \(\mathbb{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 \pi 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 \pi 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 \leq i \leq 2000\), for \(10 < p < 100\) it is \(2 \leq i \leq 500\), and for \(100 < p < 10000\) it is \(2 \leq i \leq 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 \pm 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 \(\textit{p}^i\), \(1 \leq i \leq \textit{bound}\). This is the most time consuming part in the construction of the fields.
AllFF computes all FF(p,i) for \(1 \leq i \leq \textit{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 \leq i \leq \textit{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