class group: def __init__(self, name, short_name, elts, one, mult, inv, gens): self.name = name self.elts = elts self.one = one self.mult = mult self.inv = inv self.order = len(self.elts) self.gens = gens self.short_name = short_name def __repr__(self): return self.name def elt(self, a_tuple): return group_elt(a_tuple, self) def ONE(self): return self.elt(self.one) def GENS(self): return [self.elt(aa) for aa in self.gens] class group_elt: def __init__(self, as_tuple, group): self.group = group self.as_tuple = as_tuple def __repr__(self): return str(self.as_tuple) def __mul__(self, other): result_as_tuple = self.group.mult(self.as_tuple, other.as_tuple) return group_elt(result_as_tuple, self.group) def __rmul__(self, other): result_as_tuple = self.group.mult(self.as_tuple, other) return group_elt(result_as_tuple, self.group) def __neg__(self): result_as_tuple = self.group.inv(self.as_tuple) return group_elt(result_as_tuple, self.group) def __pow__(self, m): if m == 0: return self.group.ONE() if m == 1: return self if m == 2: return self*self if m < 0: return -(self^(-m)) if m%2 == 1: return (self^(m//2))^2*self return (self^(m//2))^2 def __eq__(self, other): return self.as_tuple == other.as_tuple def cyclic_gp(p, n): name = "cyclic group of order " + str(p) + "^" + str(n) short_name = "Z/p^n" elts = [i for i in range(p^n)] one = 0 mult = lambda i1, i2: (i1 + i2) % (p ** n) inv = lambda i: (-i) % (p ** n) gens = [1] gp = group(name, short_name, elts, one, mult, inv, gens) return gp def elementary_gp(p, n): name = "(Z/" + str(p) + ")" + "^" + str(n) short_name = name pr = [list(GF(p)) for _ in range(n)] from itertools import product elts = [] for a in product(*pr): elts += [tuple(a)] one = elts[0] mult = lambda i1, i2: tuple([(i1[j] + i2[j]) % p for j in range(n)]) inv = lambda i: tuple([(-i[j]) % p for j in range(n)]) gens = [] for i in range(n): e = n*[0] e[i] = 1 gens += [tuple(e)] gp = group(name, short_name, elts, one, mult, inv, gens) return gp def heisenberg(p): name = "Heisenberg group E(" + str(p) + "^3)" short_name = "E(p^3)" elts = [(i, j, k) for i in range(p) for j in range(p) for k in range(p)] one = elts[0] mult = lambda elt1, elt2 : ((elt1[0] + elt2[0])%p, (elt1[1] + elt2[1])%p, (-elt1[1]*elt2[0] + elt1[2] + elt2[2])%p) inv = lambda elt : (p-elt[0], p-elt[1], (p - elt[2] - (p-elt[0])*(p-elt[1]))%p) gens = [(1, 0, 0), (0, 1, 0), (0, 0, 1)] gp = group(name, short_name, elts, one, mult, inv, gens) return gp def quaternion_mult(aa, bb): result = [(aa[0] + bb[0] + 2*aa[1]*bb[0])%4, (aa[1]+bb[1])%4] if result[1]%4 == 2 or result[1]%4 == 3: result[0] = (result[0] + 2)%4 result[1] = (result[1] - 2)%4 return tuple(result) def quaternion_inv(aa): result = [((-1)^(aa[0]*aa[1])*(-aa[0]))%4, (-aa[1])%4] if result[1]%4 == 2 or result[1]%4 == 3: result[0] = (result[0] + 2)%4 result[1] = (result[1] - 2)%4 return tuple(result) def quaternion_gp(): name = "Q8" short_name = name elts = [(i, j) for i in range(4) for j in range(2)] mult = quaternion_mult inv = quaternion_inv gens = [(1, 0), (0, 1)] one = (0, 0) gp = group(name, short_name, elts, one, mult, inv, gens) return gp def hypoelementary_mult(p, m, b, A, B, C, D): return ((A+C)%m, (b^C*B+D)%p) def hypoelementary_inv(p, m, b, A, B): return hypoelementary_mult(p, m, b, 0, p-B, m - A, 0) def hypoelementary(p, m, b): '''We want m | p-1 and b to be of order m in F_p.''' name = "Hypoelementary group Z/"+str(p)+"⋊ Z/"+str(m)+", glued by character 1 -->" + str(b) short_name = "Z/"+str(p)+"⋊ Z/"+str(m) elts = [(i, j) for i in range(m) for j in range(p)] mult = lambda elt1, elt2: hypoelementary_mult(p, m, b, elt1[0], elt1[1], elt2[0], elt2[1]) inv = lambda elt1 : hypoelementary_inv(p, m, b, elt1[0], elt1[1]) gens = [(1, 0), (0, 1)] one = (0, 0) gp = group(name, short_name, elts, one, mult, inv, gens) return gp