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