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)  

intresidue.py
Go to the documentation of this file.
1 from __future__ import division
2 import logging
3 import nzmath.gcd as gcd
4 import nzmath.rational as rational
5 import nzmath.ring as ring
6 import nzmath.prime as prime
7 
8 
9 _log = logging.getLogger('nzmath.intresidue')
10 
11 
13  """
14  A class for integer residue class.
15  """
16  def __init__(self, representative, modulus):
17  ring.CommutativeRingElement.__init__(self)
18  if modulus == 0:
19  raise ValueError("modulus can not be zero")
20  elif modulus < 0:
21  modulus = -modulus
22  self.m = modulus
23 
24  if isinstance(representative, (int, long)):
25  self.n = representative % self.m
26  elif all(hasattr(representative, attr) for attr in ("m", "n")):
27  assert representative.m == modulus
28  self.n = representative.n
29  elif isinstance(representative, rational.Rational):
30  t = IntegerResidueClass(representative.denominator, self.m).inverse().getResidue()
31  self.n = representative.numerator * t % self.m
32  else:
33  raise NotImplementedError("%s is not made from %s." % (self.__class__.__name__, repr(representative),))
34 
35  def __repr__(self):
36  return "IntegerResidueClass(%d, %d)" % (self.n, self.m)
37 
38  def __mul__(self, other):
39  if isinstance(other, IntegerResidueClass):
40  if self.m == other.m:
41  return self.__class__(self.n * other.n, self.m)
42  if self.m % other.m == 0:
43  return IntegerResidueClass(self.n * other.n, other.m)
44  elif other.m % self.m == 0:
45  return IntegerResidueClass(self.n * other.n, self.m)
46  else:
47  raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
48  try:
49  return self.mul_module_action(other)
50  except TypeError, e:
51  #trial may fail with TypeError.
52  #_log.debug("no action for %s * %s" % (str(self), str(other)))
53  pass
54  except AttributeError, e:
55  #trial may fail with AttributeError because other may lack ring.
56  #_log.debug("no action for %s * %s" % (str(self), str(other)))
57  pass
58  except RuntimeError, e:
59  # maximum recursion depth may exceed
60  #_log.debug("recursion limit for %s * %s" % (str(self), str(other)))
61  pass
62  return NotImplemented
63 
64  def __rmul__(self, other):
65  try:
66  return self.mul_module_action(other)
67  except TypeError, e:
68  #trial may fail with TypeError.
69  #_log.debug("no action for %s * %s" % (str(other), str(self)))
70  pass
71  except AttributeError, e:
72  #trial may fail with AttributeError because other may lack ring.
73  #_log.debug("no action for %s * %s" % (str(other), str(self)))
74  pass
75  except RuntimeError, e:
76  # maximum recursion depth may exceed
77  #_log.debug("recursion limit for %s * %s" % (str(other), str(self)))
78  pass
79  return NotImplemented
80 
81  def __div__(self, other):
82  try:
83  return self * other.inverse()
84  except AttributeError:
85  pass
86  try:
87  return self * self.__class__(other, self.m).inverse()
88  except (ValueError, NotImplementedError):
89  return NotImplemented
90 
91  __floordiv__ = __truediv__ = __div__
92 
93  def __mod__(self, other):
94  """
95  Return zero if division by other is allowed
96  """
97  return self - (self // other) * other
98 
99  def __divmod__(self, other):
100  return (self // other, self % other)
101 
102  def __rdiv__(self, other):
103  if not other:
104  return self.__class__(0, self.m)
105  else:
106  return NotImplemented
107 
108  def __add__(self, other):
109  if isinstance(other, IntegerResidueClass):
110  if self.m == other.m:
111  return self.__class__(self.n + other.n, self.m)
112  if self.m % other.m == 0:
113  return IntegerResidueClass(self.n + other.n, other.m)
114  elif other.m % self.m == 0:
115  return IntegerResidueClass(self.n + other.n, self.m)
116  else:
117  raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
118  try:
119  return self.__class__(self.n + other, self.m)
120  except:
121  return NotImplemented
122 
123  __radd__ = __add__
124 
125  def __sub__(self, other):
126  if isinstance(other, IntegerResidueClass):
127  if self.m == other.m:
128  return self.__class__(self.n - other.n, self.m)
129  if self.m % other.m == 0:
130  return IntegerResidueClass(self.n - other.n, other.m)
131  elif other.m % self.m == 0:
132  return IntegerResidueClass(self.n - other.n, self.m)
133  else:
134  raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
135  try:
136  return self.__class__(self.n - other, self.m)
137  except:
138  return NotImplemented
139 
140  def __rsub__(self, other):
141  try:
142  return self.__class__(other - self.n, self.m)
143  except:
144  return NotImplemented
145 
146  def __pow__(self, other):
147  if other < 0:
148  inverse = self.inverse()
149  return self.__class__(pow(inverse.n, -other, self.m), self.m)
150  elif other == 0:
151  return self.__class__(1, self.m)
152  else:
153  return self.__class__(pow(self.n, other, self.m), self.m)
154 
155  def __neg__(self):
156  return self.__class__(-self.n, self.m)
157 
158  def __pos__(self):
159  return self.__class__(+self.n, self.m)
160 
161  def __nonzero__(self):
162  return bool(self.n)
163 
164  def __eq__(self, other):
165  if not other and self.n == 0:
166  return True
167  if isinstance(other, IntegerResidueClass):
168  if other.m == self.m and other.n == self.n:
169  return True
170  else:
171  return False
172  return NotImplemented
173 
174  def __ne__(self, other):
175  return not (self == other)
176 
177  def __hash__(self):
178  """
179  hash so that if a == b then hash(a) == hash(b).
180  """
181  return self.n & (2**32 - 1)
182 
183  def inverse(self):
184  t = gcd.extgcd(self.n, self.m)
185  if t[2] != 1:
186  raise ZeroDivisionError("No inverse of %s." % self)
187  return self.__class__(t[0], self.m)
188 
189  def getModulus(self):
190  return self.m
191 
192  def getResidue(self):
193  return self.n
194 
196  """
197  Return the smallest non-negative representative element of the
198  residue class.
199  """
200  return rational.Integer(self.n % self.m)
201 
202  toInteger = minimumNonNegative
203 
204  def minimumAbsolute(self):
205  """
206  Return the minimum absolute representative integer of the
207  residue class.
208  """
209  result = self.n % self.m
210  if result > (self.m >> 1):
211  result -= self.m
212  return rational.Integer(result)
213 
214  def getRing(self):
215  return IntegerResidueClassRing.getInstance(self.m)
216 
217 
219  """
220  IntegerResidueClassRing is also known as Z/mZ.
221  """
222 
223  _instances = {}
224 
225  def __init__(self, modulus):
226  """
227  The argument modulus m specifies an ideal mZ.
228  """
229  ring.CommutativeRing.__init__(self)
230  self.m = modulus
231  self.registerModuleAction(rational.theIntegerRing, _mul_with_int)
232  # mathematically Q_m = Q \ {r/s; gcd(r, s) == 1, gcd(s, m) > 1}
233  # is more appropriate.
234  self.registerModuleAction(rational.theRationalField, _mul_with_rat)
235 
236  def __repr__(self):
237  return "IntegerResidueClassRing(%d)" % self.m
238 
239  def __str__(self):
240  return "Z/%dZ" % self.m
241 
242  def __hash__(self):
243  return self.m & 0xFFFFFFFF
244 
245  def card(self):
246  """
247  Return the cardinality of the ring.
248  """
249  return self.m
250 
251  @classmethod
252  def getInstance(cls, modulus):
253  """
254  getInstance returns an instance of the class of specified
255  modulus.
256  """
257 
258  if modulus not in cls._instances:
259  anInstance = IntegerResidueClassRing(modulus)
260  cls._instances[modulus] = anInstance
261  return cls._instances[modulus]
262 
263  def createElement(self, seed):
264  if isinstance(seed, IntegerResidueClass) and seed.m % self.m == 0:
265  return IntegerResidueClass(seed.n, self.m)
266  try:
267  return IntegerResidueClass(seed, self.m)
268  except:
269  raise ValueError("%s can not be converted to an IntegerResidueClass object." % seed)
270 
271  def getCharacteristic(self):
272  """
273  The characteristic of Z/mZ is m.
274  """
275  return self.m
276 
277  def __contains__(self, elem):
278  if isinstance(elem, IntegerResidueClass) and \
279  elem.getModulus() == self.m:
280  return True
281  return False
282 
283  def isfield(self):
284  """
285  isfield returns True if the modulus is prime, False if not.
286  Since a finite domain is a field, other ring property tests
287  are merely aliases of isfield.
288  """
289  if None == self.properties.isfield():
290  if prime.primeq(self.m):
291  self.properties.setIsfield(True)
292  else:
293  self.properties.setIsdomain(False)
294  return self.properties.isfield()
295 
296  isdomain = isfield
297  isnoetherian = isfield
298  isufd = isfield
299  ispid = isfield
300  iseuclidean = isfield
301 
302  def __eq__(self, other):
303  if isinstance(other, IntegerResidueClassRing) and self.m == other.m:
304  return True
305  return False
306 
307  def __ne__(self, other):
308  return not (self == other)
309 
310  def issubring(self, other):
311  if self == other:
312  return True
313  else:
314  return False
315 
316  def issuperring(self, other):
317  if self == other:
318  return True
319  else:
320  return False
321 
322  def _getOne(self):
323  "getter for one"
324  if self._one is None:
325  self._one = IntegerResidueClass(1, self.m)
326  return self._one
327 
328  one = property(_getOne, None, None, "multiplicative unit.")
329 
330  def _getZero(self):
331  "getter for zero"
332  if self._zero is None:
333  self._zero = IntegerResidueClass(0, self.m)
334  return self._zero
335 
336  zero = property(_getZero, None, None, "additive unit.")
337 
338 
339 def _mul_with_int(integer, residue):
340  """
341  Return k * IntegerResidueClass(n, m)
342  """
343  return residue.__class__(integer * residue.n, residue.m)
344 
345 def _mul_with_rat(rat, residue):
346  """
347  Return Rational(a, b) * IntegerResidueClass(n, p)
348  """
349  return residue.__class__(rat * residue.n, residue.m)
nzmath.intresidue.IntegerResidueClassRing.__ne__
def __ne__(self, other)
Definition: intresidue.py:307
nzmath.ring
Definition: ring.py:1
nzmath.intresidue.IntegerResidueClass.__nonzero__
def __nonzero__(self)
Definition: intresidue.py:161
nzmath.intresidue.IntegerResidueClassRing.__repr__
def __repr__(self)
Definition: intresidue.py:236
nzmath.intresidue._mul_with_int
def _mul_with_int(integer, residue)
Definition: intresidue.py:339
nzmath.intresidue.IntegerResidueClass.__add__
def __add__(self, other)
Definition: intresidue.py:108
nzmath.intresidue.IntegerResidueClassRing
Definition: intresidue.py:218
nzmath.intresidue.IntegerResidueClass.__rmul__
def __rmul__(self, other)
Definition: intresidue.py:64
nzmath.intresidue.IntegerResidueClassRing.__eq__
def __eq__(self, other)
Definition: intresidue.py:302
nzmath.intresidue.IntegerResidueClass.__ne__
def __ne__(self, other)
Definition: intresidue.py:174
nzmath.intresidue.IntegerResidueClass.__sub__
def __sub__(self, other)
Definition: intresidue.py:125
nzmath.intresidue.IntegerResidueClass.getResidue
def getResidue(self)
Definition: intresidue.py:192
nzmath.intresidue.IntegerResidueClass.__hash__
def __hash__(self)
Definition: intresidue.py:177
nzmath.gcd
Definition: gcd.py:1
nzmath.intresidue.IntegerResidueClassRing._zero
_zero
Definition: intresidue.py:333
nzmath.intresidue.IntegerResidueClassRing.__contains__
def __contains__(self, elem)
Definition: intresidue.py:277
nzmath.intresidue.IntegerResidueClass.__divmod__
def __divmod__(self, other)
Definition: intresidue.py:99
nzmath.intresidue.IntegerResidueClassRing.m
m
Definition: intresidue.py:230
nzmath.rational
Definition: rational.py:1
nzmath.intresidue.IntegerResidueClass.getModulus
def getModulus(self)
Definition: intresidue.py:189
nzmath.intresidue.IntegerResidueClass.__rdiv__
def __rdiv__(self, other)
Definition: intresidue.py:102
nzmath.intresidue.IntegerResidueClass.minimumAbsolute
def minimumAbsolute(self)
Definition: intresidue.py:204
nzmath.ring.CommutativeRing
Definition: ring.py:88
nzmath.intresidue.IntegerResidueClassRing.isfield
def isfield(self)
Definition: intresidue.py:283
nzmath.ring.CommutativeRingElement.mul_module_action
def mul_module_action(self, other)
Definition: ring.py:305
nzmath.rational.Rational
Definition: rational.py:10
nzmath.intresidue.IntegerResidueClass
Definition: intresidue.py:12
nzmath.intresidue.IntegerResidueClass.inverse
def inverse(self)
Definition: intresidue.py:183
nzmath.intresidue.IntegerResidueClass.__neg__
def __neg__(self)
Definition: intresidue.py:155
nzmath.intresidue.IntegerResidueClassRing.createElement
def createElement(self, seed)
Definition: intresidue.py:263
nzmath.intresidue.IntegerResidueClassRing.card
def card(self)
Definition: intresidue.py:245
nzmath.intresidue._mul_with_rat
def _mul_with_rat(rat, residue)
Definition: intresidue.py:345
nzmath.ring.CommutativeRingElement
Definition: ring.py:291
nzmath.intresidue.IntegerResidueClass.__rsub__
def __rsub__(self, other)
Definition: intresidue.py:140
nzmath.intresidue.IntegerResidueClass.__pos__
def __pos__(self)
Definition: intresidue.py:158
nzmath.intresidue.IntegerResidueClass.__mod__
def __mod__(self, other)
Definition: intresidue.py:93
nzmath.intresidue.IntegerResidueClassRing.__init__
def __init__(self, modulus)
Definition: intresidue.py:225
nzmath.prime
Definition: prime.py:1
nzmath.rational.Integer
Definition: rational.py:639
nzmath.intresidue.IntegerResidueClass.__repr__
def __repr__(self)
Definition: intresidue.py:35
nzmath.intresidue.IntegerResidueClassRing.getCharacteristic
def getCharacteristic(self)
Definition: intresidue.py:271
nzmath.intresidue.IntegerResidueClassRing.__str__
def __str__(self)
Definition: intresidue.py:239
nzmath.intresidue.IntegerResidueClass.__pow__
def __pow__(self, other)
Definition: intresidue.py:146
nzmath.intresidue.IntegerResidueClassRing.getInstance
def getInstance(cls, modulus)
Definition: intresidue.py:252
nzmath.intresidue.IntegerResidueClass.__eq__
def __eq__(self, other)
Definition: intresidue.py:164
nzmath.intresidue.IntegerResidueClassRing.__hash__
def __hash__(self)
Definition: intresidue.py:242
nzmath.intresidue.IntegerResidueClassRing._one
_one
Definition: intresidue.py:325
nzmath.intresidue.IntegerResidueClassRing.issuperring
def issuperring(self, other)
Definition: intresidue.py:316
nzmath.intresidue.IntegerResidueClass.n
n
Definition: intresidue.py:25
nzmath.ring.CommutativeRing.properties
properties
Definition: ring.py:103
nzmath.intresidue.IntegerResidueClass.getRing
def getRing(self)
Definition: intresidue.py:214
nzmath.intresidue.IntegerResidueClassRing.issubring
def issubring(self, other)
Definition: intresidue.py:310
nzmath.intresidue.IntegerResidueClass.minimumNonNegative
def minimumNonNegative(self)
Definition: intresidue.py:195
nzmath.intresidue.IntegerResidueClass.__init__
def __init__(self, representative, modulus)
Definition: intresidue.py:16
nzmath.intresidue.IntegerResidueClass.__mul__
def __mul__(self, other)
Definition: intresidue.py:38
nzmath.intresidue.IntegerResidueClassRing._getOne
def _getOne(self)
Definition: intresidue.py:322
nzmath.intresidue.IntegerResidueClassRing._getZero
def _getZero(self)
Definition: intresidue.py:330
nzmath.intresidue.IntegerResidueClass.m
m
Definition: intresidue.py:22
nzmath.intresidue.IntegerResidueClass.__div__
def __div__(self, other)
Definition: intresidue.py:81
nzmath.intresidue.IntegerResidueClassRing._instances
dictionary _instances
Definition: intresidue.py:223
nzmath.ring.CommutativeRing.registerModuleAction
def registerModuleAction(self, action_ring, action)
Definition: ring.py:156