NZMATH  1.2.0
About: NZMATH is a Python based number theory oriented calculation system.
  Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

group.py
Go to the documentation of this file.
1 """
2 Group Theorical module
3 """
4 import math
5 import nzmath.rational as rational
6 import nzmath.factor.misc as factor_misc
7 import nzmath.vector as vector
8 import nzmath.matrix as matrix
10 
11 
12 class Group:
13  """
14  This is a class for finite group.
15  """
16 
17  def __init__(self, value, operation=-1):
18  if isinstance(value, Group):
19  self.entity = value.entity
20  if operation == -1:
21  self.operation = value.operation
22  else:
23  self.setOperation(operation)
24  else:
25  self.entity = value
26  if operation == -1:
27  self.setOperation(0)
28  else:
29  self.setOperation(operation)
30 
31  def __repr__(self):
32  if hasattr(self.entity, "__repr__"):
33  return self.entity.__repr__()
34  else:
35  return repr(self.entity.__class__.__name__)
36 
37  def __str__(self):
38  if hasattr(self.entity, "__str__"):
39  return self.entity.__str__()
40  else:
41  return str(self.entity.__class__.__name__)
42 
43  def __eq__(self, other):
44  if self.entity == other.entity and self.operation == other.operation:
45  return True
46  else:
47  return False
48 
49  def __ne__(self, other):
50  return not (self == other)
51 
52  def setOperation(self, value):
53  """
54  Change group type for additive(0) or multiplicative(1).
55  """
56  if isinstance(value, int) :
57  self.operation = (value & 1)
58  else:
59  raise TypeError("invalid input")
60 
61  def createElement(self, *value):
62  """
63  Create group element with value.
64  Return GroupElement instance.
65  """
66  return GroupElement(self.entity.createElement(*value), self.operation)
67 
68  def identity(self):
69  """
70  Return identity element(unit).
71  Return addtive 0 or multiplicative 1.
72  """
73  if hasattr(self.entity, "identity"):
74  return GroupElement(self.entity.identity(), self.operation)
75  else:
76  if self.operation:
77  return GroupElement(self.entity.one, 1)
78  else:
79  return GroupElement(self.entity.zero, 0)
80 
81  def grouporder(self):
82  """
83  Return group order(Cardinality).
84  """
85  order = 0
86  if hasattr(self.entity, "grouporder"):
87  order = self.entity.grouporder()
88  elif hasattr(self.entity, "card"):
89  order = card(self.entity)
90  else:
91  order = self.entity.m
92  if self.operation and hasattr(self.entity, "zero"): # *-group
93  order -= 1
94  return order
95 
96 
98  """
99  This is a class for finite group element.
100  """
101 
102  def __init__(self, value, operation=-1):
103  self.operation = operation
104  if isinstance(value, GroupElement):
105  self.entity = value.entity
106  self.set = value.set
107  self._set_name = value._set_name
108  if operation == -1:
109  self.operation = value.operation
110  else:
111  self.setOperation(operation)
112  else:
113  self.entity = value
114  if operation == -1:
115  if self._type_check(1):
116  self.operation = 1
117  if self._type_check(0):
118  self.operation = 0
119  if self.operation == -1:
120  raise TypeError("This element isn't Group")
121  self.set = self.getGroup()
122  self.setOperation(self.operation) # mainly operation
123  self._set_name = self.set.entity.__class__.__name__
124 
125  def __repr__(self):
126  return self._set_name + ',' + repr(self.entity)
127 
128  def __str__(self):
129  return self._set_name + ',' + str(self.entity)
130 
131  def __eq__(self, other):
132  if self.entity == other.entity and self.operation == other.operation:
133  return True
134  else:
135  return False
136 
137  def __ne__(self, other):
138  return not (self == other)
139 
140  def _type_check(self, value):
141  """
142  Check group type is value or not.
143  """
144  a = self.entity
145  if not (value & 1):
146  if hasattr(a, "__add__") and hasattr(a, "__mul__"):
147  return True
148  else:
149  return False
150  else:
151  if hasattr(a, "__mul__") and hasattr(a, "__pow__"):
152  return True
153  else:
154  return False
155 
156  def setOperation(self, value):
157  """
158  Change group type for additive(0) or multiplicative(1).
159  """
160  if isinstance(value, int) and self._type_check(value):
161  self.operation = (value & 1)
162  else:
163  raise TypeError("invalid input")
164  self.set.setOperation(self.operation)
165 
166  def ope(self, other):
167  """
168  Group basic operation.
169  """
170  if not self.operation:
171  return GroupElement(self.entity + other.entity, self.operation)
172  else:
173  return GroupElement(self.entity * other.entity, self.operation)
174 
175  def ope2(self, other):
176  """
177  Group extended operation
178  """
179  if rational.isIntegerObject(other):
180  if not self.operation:
181  return GroupElement(self.entity * other, self.operation)
182  else:
183  return GroupElement(self.entity ** other, self.operation)
184  else:
185  raise TypeError("input integer")
186 
187  def inverse(self):
188  """
189  Return inverse element.
190  """
191  ele = self.entity
192  cla = self.set
193  operation = self.operation
194  if hasattr(cla.entity, "zero") and (ele == cla.entity.zero):
195  return self
196  else:
197  if not operation:
198  return GroupElement(-ele, operation)
199  elif hasattr(ele, "inverse"):
200  return GroupElement(ele.inverse(), operation)
201  else:
202  return GroupElement(self.ope2(cla.order() - 1), operation)
203 
204  def order(self):
205  """
206  Compute order using grouporder factorization.
207  """
208  clas = self.set.entity
209  if hasattr(clas, "zero") and self.entity == clas.zero:
210  return 1
211  ordfact = factor_misc.FactoredInteger(self.set.grouporder())
212  identity = self.set.identity()
213  k = 1
214  for p, e in ordfact:
215  b = self.ope2(int(ordfact) // (p ** e))
216  while b != identity:
217  k = k * p
218  b = b.ope2(p)
219  return k
220 
221  def t_order(self, v=2):
222  """
223  Compute order using Terr's Baby-step Giant-step algorithm.
224  """
225  if (v < 1) or not(rational.isIntegerObject(v)):
226  raise TypeError("input integer v >= 1")
227  e = self.set.identity()
228  a = self.set.identity()
229  R = [(e, 0)]
230  for i in range(1, v + 1):
231  a = self.ope(a)
232  if a == e:
233  return i
234  else:
235  R.append((a, i))
236  j = 0
237  b = a.ope2(2)
238  t = 2 * v
239  while True:
240  for (c, k) in R:
241  if b == c:
242  return (t - k)
243  a = self.ope(a)
244  j += 1
245  R.append((a, j + v))
246  b = a.ope(b)
247  t += j + v
248 
249  def getGroup(self):
250  """
251  Return the group which element belongs.
252  """
253  if self._type_check(0) and self._type_check(1):
254  if hasattr(self.entity, "getRing"):
255  return Group(self.entity.getRing(), self.operation)
256  else:
257  return Group(self.entity, self.operation)
258  else:
259  if hasattr(self.entity, "getGroup"):
260  return Group(self.entity.getGroup(), self.operation)
261  else:
262  return Group(self.entity, self.operation)
263 
264 
266  """
267  This is a class for finite group with generator.
268  """
269 
270  def __init__(self, value, operation=-1, entity=None):
271  if isinstance(value, list):
272  temp = value
273  else:
274  TypeError("invalid input")
275  if entity:
276  self.entity = entity
277  else:
278  self.entity = GroupElement(value[0]).set.entity
279  self.generator = []
280  for a in temp:
281  self.generator.append(GroupElement(a))
282  if operation == -1:
283  self.operation = self.generator[0].operation
284  else:
285  self.setOperation(operation)
286 
287  def isGroupElement(self, other):
288  """
289  Check whether other is self group element or not.
290  """
291  pass
292 
293  def setOperation(self, value):
294  """
295  Change group type for additive(0) or multiplicative(1).
296  """
297  if isinstance(value, int) :
298  self.operation = (value & 1)
299  else:
300  raise TypeError("invalid input")
301  for a in self.generator:
302  a.setOperation(value)
303 
304 
306  """
307  This is a class for finite abelian group with genarator.
308  """
309 
310  def relationLattice(self):
311  """
312  Return relation lattice basis as column vector matrix for generator.
313  If B[j]=transpose(b[1,j],b[2,j],..,b[l,j]),
314  it satisfies that product(generator[i]**b[i,j])=1 for each j.
315  """
316  if not hasattr(self, "relation"):
317  l = len(self.generator)
319  H1 = [(self.identity(), vector.Vector([0] * l))]
320  H2 = list(H1)
321  m = 1
322  a_baby_s, giant_s = list(H1), list(H2)
323  pro_I1, pro_I2, pro_diag = 1, 1, 1
324  e_vec = []
325  g_gen = []
326  for i in range(1, l + 1):
327  e_i = vector.Vector([0] * l)
328  e_i[i] = 1
329  e_vec.append(e_i)
330  g_gen.append(self.generator[i - 1])
331  for j in range(1, l + 1):
332  e = 1
333  baby_s = list(a_baby_s)
334  baby_e = GroupElement(g_gen[j - 1])
335  giant_e = GroupElement(g_gen[j - 1])
336  flag = False
337  while not flag:
338  for (g_g, v) in giant_s:
339  for (g_b, w) in baby_s:
340  if g_g.ope(giant_e) == g_b:
341  b[j] = v + w + (e * (e + 1) >> 1) * e_vec[j - 1]
342  flag = True
343  break
344  if flag:
345  break
346  if flag:
347  break
348  for (g_a, v_a) in a_baby_s:
349  baby_s.append((g_a.ope(baby_e), v_a - e * e_vec[j - 1]))
350  e += 1
351  baby_e = baby_e.ope(g_gen[j - 1])
352  giant_e = giant_e.ope(baby_e)
353  if (j < l) and (b[j, j] > 1):
354  pro_diag *= b[j, j]
355  pro_diag_root = math.sqrt(pro_diag)
356  if (b[j, j] * pro_I1) <= pro_diag_root or j == 1:
357  temp = list(H1)
358  for (g, v) in temp:
359  g_j_inv = g_gen[j - 1].inverse()
360  H1_1 = GroupElement(g)
361  for x in range(1, b[j, j]):
362  H1_1 = H1_1.ope(g_j_inv)
363  H1.append((H1_1, v + x * e_vec[j - 1]))
364  pro_I1 *= b[j, j]
365  else:
366  if m > 1:
367  temp = list(H2)
368  for (g, v) in temp:
369  H2_1 = GroupElement(g)
370  for x in range(1, b[m, m]):
371  H2_1 = H2_1.ope(g_gen[m - 1])
372  H2.append((H2_1, v + x * e_vec[m - 1]))
373  pro_I2 *= b[m, m]
374  m = j
375  s = int(math.ceil(pro_diag_root / pro_I1))
376  if len(H2) > 1:
377  t = int(math.ceil(pro_diag_root / pro_I2))
378  else:
379  t = 1
380  a_baby_s, giant_s = list(H1), list(H2)
381  g_m_inv = g_gen[m - 1].inverse()
382  for (h1, v) in H1:
383  H1_1 = GroupElement(h1)
384  for r in range(1, s):
385  H1_1 = H1_1.ope(g_m_inv)
386  a_baby_s.append((H1_1, v + r * e_vec[m - 1]))
387  g_m_s = g_gen[m - 1].ope2(s)
388  for (h2, v) in H2:
389  H2_1 = GroupElement(h2)
390  for q in range(1, t):
391  H2_1 = H2_1.ope(g_m_s)
392  giant_s.append((H2_1, v + (q * s) * e_vec[m - 1]))
393  self.relation = b
394  return self.relation
395 
396  def computeStructure(self):
397  """
398  Compute Finite Abelian Group Structure.
399  """
400  B = self.relationLattice()
401  U_d, V, M = B.extsmithNormalForm()
402  det = M.determinant()
403  U_d.toFieldMatrix()
404  U = U_d.inverse()
405  for i in range(U_d.row):
406  U_d[i] = (U_d[i] % det)
407  structure = []
408  l = M.row
409  for j in range(1, l):
410  if M[j, j] != 1 or j == 1:
411  g = self.identity()
412  for i in range(1, l+1):
413  g = g.ope(self.generator[i-1].ope2(int(U[i, j])))
414  structure.append((g, M[j, j]))
415  else:
416  break
417  return structure, det
nzmath.group.Group
Definition: group.py:12
nzmath.bigrange.range
def range(start, stop=None, step=None)
Definition: bigrange.py:19
nzmath.group.GroupElement.set
set
Definition: group.py:106
nzmath.factor.misc
Definition: misc.py:1
nzmath.group.Group.__ne__
def __ne__(self, other)
Definition: group.py:49
nzmath.group.GroupElement._set_name
_set_name
Definition: group.py:107
nzmath.group.GroupElement.__eq__
def __eq__(self, other)
Definition: group.py:131
nzmath.group.GroupElement.inverse
def inverse(self)
Definition: group.py:187
nzmath.group.GroupElement.__str__
def __str__(self)
Definition: group.py:128
nzmath.group.AbelianGenerate.computeStructure
def computeStructure(self)
Definition: group.py:396
nzmath.group.AbelianGenerate.relation
relation
Definition: group.py:393
nzmath.matrix
Definition: matrix.py:1
nzmath.group.Group.__repr__
def __repr__(self)
Definition: group.py:31
nzmath.group.GroupElement.operation
operation
Definition: group.py:103
nzmath.group.Group.entity
entity
Definition: group.py:19
nzmath.group.GenerateGroup.__init__
def __init__(self, value, operation=-1, entity=None)
Definition: group.py:270
nzmath.group.GroupElement.__ne__
def __ne__(self, other)
Definition: group.py:137
nzmath.rational
Definition: rational.py:1
nzmath.group.GroupElement
Definition: group.py:97
nzmath.group.GroupElement.order
def order(self)
Definition: group.py:204
nzmath.group.GenerateGroup.setOperation
def setOperation(self, value)
Definition: group.py:293
nzmath.vector.Vector
Definition: vector.py:3
nzmath.group.GenerateGroup.isGroupElement
def isGroupElement(self, other)
Definition: group.py:287
nzmath.group.Group.__str__
def __str__(self)
Definition: group.py:37
nzmath.group.Group.identity
def identity(self)
Definition: group.py:68
nzmath.group.GroupElement.t_order
def t_order(self, v=2)
Definition: group.py:221
nzmath.group.GroupElement.__repr__
def __repr__(self)
Definition: group.py:125
nzmath.vector
Definition: vector.py:1
nzmath.group.GroupElement.entity
entity
Definition: group.py:105
nzmath.matrix.RingSquareMatrix
Definition: matrix.py:860
nzmath.arith1.inverse
def inverse(x, n)
Definition: arith1.py:183
nzmath.group.GroupElement.ope2
def ope2(self, other)
Definition: group.py:175
nzmath.compatibility
Definition: compatibility.py:1
nzmath.group.GroupElement.setOperation
def setOperation(self, value)
Definition: group.py:156
nzmath.group.GroupElement.getGroup
def getGroup(self)
Definition: group.py:249
nzmath.group.AbelianGenerate
Definition: group.py:305
nzmath.group.GroupElement.ope
def ope(self, other)
Definition: group.py:166
nzmath.group.Group.__eq__
def __eq__(self, other)
Definition: group.py:43
nzmath.group.GenerateGroup.generator
generator
Definition: group.py:279
nzmath.group.Group.operation
operation
Definition: group.py:21
nzmath.group.GroupElement._type_check
def _type_check(self, value)
Definition: group.py:140
nzmath.ring.getRing
def getRing(obj)
Definition: ring.py:809
nzmath.group.GenerateGroup
Definition: group.py:265
nzmath.group.Group.__init__
def __init__(self, value, operation=-1)
Definition: group.py:17
nzmath.group.Group.setOperation
def setOperation(self, value)
Definition: group.py:52
nzmath.group.AbelianGenerate.relationLattice
def relationLattice(self)
Definition: group.py:310
nzmath.group.GroupElement.__init__
def __init__(self, value, operation=-1)
Definition: group.py:102
nzmath.group.Group.createElement
def createElement(self, *value)
Definition: group.py:61
nzmath.compatibility.card
def card(virtualset)
Definition: compatibility.py:28
nzmath.group.Group.grouporder
def grouporder(self)
Definition: group.py:81