Welcome, guest | Sign In | My Account | Store | Cart
```"""
A module for finite arithmetic.
"""

#Import generators.
from __future__ import generators

__version__ = '1.0'
__needs__ = '2.2'
__author__ = "G. Rodrigues"

#The stupidest prime-detection algorithm possible.
def IsPrime(n):
if isinstance(n, int) and n >= 1:
for i in range(2, n):
if not n%i
return 0
return 1
else:
raise TypeError("%r is not an integer >= 1." % n)

#Auxiliary constructor functions.
def _ret_new(n):
def _new(cls, m):
if isinstance(m, int):
return int.__new__(cls, m%n)
else:
raise TypeError("%r is not an integer." % m)
return _new

def _ret_str():
def _str(m):
return int.__str__(m)
return _str

def _ret_nonzero():
def _nonzero(m):
return int.__nonzero__(m)
return _nonzero

def _ret_hash():
def _hash(m):
return int.__hash__(m)
return _hash

def _ret_cmp():
def _cmp(m, p):
return int.__cmp__(m, p)
return _cmp

def _ret_neg():
def _neg(m):
return m.__class__(int.__neg__(m))
return _neg

def _ret_sub():
def _sub(m, p):
return p.__class__(int.__sub__(m, p))
return _sub

def _ret_rsub():
def _rsub(m, p):
return p.__sub__(m)
return _rsub

def _ret_mul():
def _mul(m, p):
return p.__class__(int.__mul__(m, p))
return _mul

def _ret_rmul():
def _rmul(m, p):
return p.__mul__(m)
return _rmul

def _ret_div():
def _div(m, p):
if p:
return p.__class__(int.__mul__(m, p.__invert__()))
else:
raise ZeroDivisionError("Cannot divide by zero.")
return _div

def _ret_rdiv():
def _rdiv(m, p):
return p.__div__(m)
return _rdiv

def _ret_inv(n):
def _inv(m):
if m:
#Initialize variables.
o = (m, n)
ret = (0, 1)
r = m % n
q = m // n

#Main loop.
while 1:
#Are we finished?
if r:
o = o[-1], r
r = o[0] % o[1]
q = o[0] // o[1]
ret = ret[-1], ret[0] - q*ret[1]
else:
return m.__class__(ret[0])
else:
raise ZeroDivisionError("Cannot invert 0 in any field.")
return _inv

class Field(type):
"""The Finite Field metaclass.

For each integer n > 1, Field(n) returns the finite ring of integers modulo n."""

def __new__(cls, n):
if isinstance(n, int) and n > 1:
#Initialize methods dictionary and add the methods one by one.
meth = {}

meth['__new__'] = staticmethod(_ret_new(n))
meth['__str__'] = _ret_str()
meth['__nonzero__'] = _ret_nonzero()
meth['__hash__'] = _ret_hash()
meth['__cmp__'] = _ret_cmp()

#Algebraic ring operations.
meth['__neg__'] = _ret_neg()
meth['__sub__'] = _ret_sub()
meth['__rsub__'] = _ret_rsub()
meth['__mul__'] = _ret_mul()
meth['__rmul__'] = _ret_rmul()

#If n is prime add division.
if IsPrime(n):
meth['__invert__'] = _ret_inv(n)
meth['__div__'] = _ret_div()
meth['__rdiv__'] = _ret_rdiv()

return type.__new__(cls, "Z(%d)" % n, (int,), meth)
else:
raise TypeError("%s is not an integer > 1." % n)

def __init__(self, n):
#Generate docstring.
self.__doc__ = "The Z(%d) finite field." % n

def __str__(self):
return self.__name__

def __len__(self):
return int(self.__name__[2:-1])

def __iter__(self):
for i in xrange(len(self)):
yield self(i)

#Auxiliary functions that build the operation tables.
def cartesian_product(list1, list2):
"""Returns the cartesian product of the lists."""
ret = []
for i in list1:
ret.append([(i, j) for j in list2])
return ret

def build_table(ring, unboundmethod):
"""Displays the table for the given operation of the ring."""
list_elems = list(ring)
print "   " + " | ".join([str(i) for i in list_elems])

#Main loop.
for lst in cartesian_product(list_elems, list_elems):
temp = []
for i, j in lst:
temp.append(unboundmethod(i, j))
print ("%s| " % lst[0][0]) + " | ".join([str(i) for i in temp])

def build_div(ring):
"""Displays the table for division in the ring."""
list_elems = list(ring)
print "   " + " | ".join([str(i) for i in list_elems])

#Main loop.
for lst in cartesian_product(list_elems, list_elems):
temp = []
for i, j in lst:
try:
result = i / j
except ZeroDivisionError:
temp.append('X')
else:
temp.append(result)
print ("%s| " % lst[0][0]) + " | ".join([str(i) for i in temp])

#Some test code.
if __name__ == "__main__":
#Construct rings.
rings = [Field(i) for i in range(2, 10)]

for ring in rings:
#Test classes.
print "This is the finite ring %s." % ring
print "It has elements: %s." % list(ring)
#Display tables.
print "The addition table is:"
print "The multiplication table is:"
build_table(ring, ring.__mul__)
if IsPrime(len(ring)):
print "The division table is:"
build_div(ring)
else:
print "The ring %s is not a Field." % ring
print '\n'

#Test silent conversions to int.
ints = range(len(rings[-1]))
for i, j in zip(ints, list(rings[-1])):
print "%s + %s = %s with type %s." % (i, j, i + j, type(i + j))
```