1############################################################################
2##
3##  util.gi                       IRREDSOL                  Burkhard Höfling
4##
5##  Copyright © 2003–2016 Burkhard Höfling
6##
7
8
9############################################################################
10##
11#I  TestFlag(<n>, <i>)
12##
13##  tests if the i-th bit is set in binary representation the nonnegative
14##  integer n
15##
16InstallGlobalFunction(TestFlag,
17    function(n, i)
18        return QuoInt(n, 2^i) mod 2 = 1;
19    end);
20
21
22############################################################################
23##
24#F  CodeCharacteristicPolynomial(<mat>, <q>)
25##
26##  given a matrix mat over GF(q), this computes a number which uniquely
27##  identifies the characteristic polynomial of mat.
28##
29InstallGlobalFunction(CodeCharacteristicPolynomial,
30    function(mat, q)
31
32        local cf, z, sum, c;
33
34        z := Z(q);
35        if Length(mat) = 2 then
36            cf := [ mat[1][1]*mat[2][2] - mat[1][2]*mat[2][1],
37                    - mat[1][1] - mat[2][2],
38                    z^0];
39        elif Length(mat) = 3 then
40            cf := [ - mat[1][1]*mat[2][2]*mat[3][3] - mat[1][2]*mat[2][3]*mat[3][1] - mat[1][3]*mat[2][1]*mat[3][2]
41                    + mat[1][1]*mat[2][3]*mat[3][2] + mat[2][2]*mat[1][3]*mat[3][1] + mat[3][3]*mat[2][1]*mat[1][2],
42                    mat[1][1]*mat[2][2] + mat[2][2]*mat[3][3] + mat[1][1]*mat[3][3]
43                        - mat[1][2]*mat[2][1] - mat[2][3]*mat[3][2] - mat[1][3]*mat[3][1],
44                    - mat[1][1] - mat[2][2] - mat[3][3],
45                    z^0];
46        else
47            cf := CoefficientsOfUnivariatePolynomial(CharacteristicPolynomial(mat, 1));
48        fi;
49
50        sum := 0;
51        for c in cf do
52            if c = 0*z then
53                sum := sum * q;
54            else
55                sum := sum * q + LogFFE(c, z) + 1;
56            fi;
57        od;
58
59        return sum;
60    end);
61
62
63############################################################################
64##
65#F  FFMatrixByNumber(n, d, q)
66##
67##  computes a d x d matrix over GF(q) represented by the integer n
68##
69InstallGlobalFunction(FFMatrixByNumber,
70    function(n, d, q)
71
72        local z, m, i, j, k;
73
74        z := Z(q);
75        m := NullMat(d,d, GF(q));
76
77        for i in [d, d-1..1] do
78            for j in [d, d-1..1] do
79                k := RemInt(n, q);
80                n := QuoInt(n, q);
81                if k > 0 then
82                    m[i][j] := z^(k-1);
83                fi;
84            od;
85        od;
86        ConvertToMatrixRep(m, q);
87        return m;
88    end);
89
90
91############################################################################
92##
93#F  CanonicalPcgsByNumber(<pcgs>, <n>)
94##
95##  computes the canonical pcgs wrt. pcgs represented by the integer n
96##
97InstallGlobalFunction(CanonicalPcgsByNumber,
98    function(pcgs, n)
99
100        local gens, cpcgs;
101
102        gens := List(ExponentsCanonicalPcgsByNumber(RelativeOrders(pcgs), n),
103            exp -> PcElementByExponents(pcgs, exp));
104        cpcgs := InducedPcgsByPcSequenceNC(pcgs, gens);
105        SetIsCanonicalPcgs(cpcgs, true);
106        return cpcgs;
107    end);
108
109
110############################################################################
111##
112#F  OrderGroupByCanonicalPcgsByNumber(<pcgs>, <n>)
113##
114##  computes Order(Group(CanonicalPcgsByNumber(<pcgs>, <n>))) without
115##  actually constructing the canonical pcgs or the group
116##
117InstallGlobalFunction(OrderGroupByCanonicalPcgsByNumber,
118    function(pcgs, n)
119
120        local ros, order, j;
121
122        order := 1;
123        ros := RelativeOrders(pcgs);
124        n := RemInt(n, 2^Length(ros));
125        for j in [1..Length(ros)] do
126            if RemInt(n, 2) > 0 then
127                order := order * ros[j];
128            fi;
129            n := QuoInt(n, 2);
130        od;
131        return order;
132    end);
133
134
135############################################################################
136##
137#F  ExponentsCanonicalPcgsByNumber(<ros>, <n>)
138##
139##  computes the list of exponent vectors of the
140##  elements of CanonicalPcgsByNumber(<pcgs>, <n>)) without actually
141##  constructing the canonical pcgs itself - it is enough to know the
142##  relative orders of the pc elements
143##
144InstallGlobalFunction(ExponentsCanonicalPcgsByNumber,
145    function(ros, n)
146
147        local depths, len, d, exps, exp, j, cpcgs;
148        depths := [];
149        len := Length(ros);
150        for j in [1..len] do
151            d := RemInt(n, 2);
152            n := QuoInt(n, 2);
153            if d > 0 then
154                Add(depths, j);
155            fi;
156        od;
157
158        exps := [];
159        for d in depths do
160            exp := ListWithIdenticalEntries(len, 0);
161            exp[d] := 1;
162            for j in [d+1..len] do
163                if not j in depths then
164                    exp[j] := RemInt(n, ros[j]);
165                    n := QuoInt(n, ros[j]);
166                fi;
167            od;
168            Add(exps, exp);
169        od;
170
171        return exps;
172    end);
173
174
175############################################################################
176##
177#F  IsMatGroupOverFieldFam(famG, famF)
178##
179##  tests whether famG is the collections family of matrices over the field
180##  whose family is famF
181##
182InstallGlobalFunction(IsMatGroupOverFieldFam, function(famG, famF)
183    return CollectionsFamily(CollectionsFamily(famF)) = famG;
184end);
185
186
187############################################################################
188##
189#V  IRREDSOL_DATA.PRIME_POWERS
190##
191##  cache of proper prime powers, preset to all prime powers <= 65535
192##
193IRREDSOL_DATA.PRIME_POWERS :=
194[ 4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 121, 125, 128, 169, 243, 256, 289,
195  343, 361, 512, 529, 625, 729, 841, 961, 1024, 1331, 1369, 1681, 1849, 2048,
196  2187, 2197, 2209, 2401, 2809, 3125, 3481, 3721, 4096, 4489, 4913, 5041,
197  5329, 6241, 6561, 6859, 6889, 7921, 8192, 9409, 10201, 10609, 11449, 11881,
198  12167, 12769, 14641, 15625, 16129, 16384, 16807, 17161, 18769, 19321,
199  19683, 22201, 22801, 24389, 24649, 26569, 27889, 28561, 29791, 29929,
200  32041, 32761, 32768, 36481, 37249, 38809, 39601, 44521, 49729, 50653,
201  51529, 52441, 54289, 57121, 58081, 59049, 63001 ];
202
203
204############################################################################
205##
206#F  IsPPowerInt(q)
207##
208##  tests whether q is a positive prime power, caching new prime powers
209##
210InstallGlobalFunction(IsPPowerInt,
211    function(q)
212        if not IsPosInt(q) then
213            return false;
214        elif IsPrimeInt(q) then
215            return true;
216        elif q in IRREDSOL_DATA.PRIME_POWERS then
217            return true;
218        elif IsPrimePowerInt(q) then
219            AddSet(IRREDSOL_DATA.PRIME_POWERS, q);
220            return true;
221        else
222            return false;
223        fi;
224    end);
225
226
227############################################################################
228##
229#E
230##
231