Lib/lib-old/zmod.py

   1 # module 'zmod'
   2
   3 # Compute properties of mathematical "fields" formed by taking
   4 # Z/n (the whole numbers modulo some whole number n) and an
   5 # irreducible polynomial (i.e., a polynomial with only complex zeros),
   6 # e.g., Z/5 and X**2 + 2.
   7 #
   8 # The field is formed by taking all possible linear combinations of
   9 # a set of d base vectors (where d is the degree of the polynomial).
  10 #
  11 # Note that this procedure doesn't yield a field for all combinations
  12 # of n and p: it may well be that some numbers have more than one
  13 # inverse and others have none.  This is what we check.
  14 #
  15 # Remember that a field is a ring where each element has an inverse.
  16 # A ring has commutative addition and multiplication, a zero and a one:
  17 # 0*x = x*0 = 0, 0+x = x+0 = x, 1*x = x*1 = x.  Also, the distributive
  18 # property holds: a*(b+c) = a*b + b*c.
  19 # (XXX I forget if this is an axiom or follows from the rules.)
  20
  21 import poly
  22
  23
  24 # Example N and polynomial
  25
  26 N = 5
  27 P = poly.plus(poly.one(0, 2), poly.one(2, 1)) # 2 + x**2
  28
  29
  30 # Return x modulo y.  Returns >= 0 even if x < 0.
  31
  32 def mod(x, y):
  33         return divmod(x, y)[1]
  34
  35
  36 # Normalize a polynomial modulo n and modulo p.
  37
  38 def norm(a, n, p):
  39         a = poly.modulo(a, p)
  40         a = a[:]
  41         for i in range(len(a)): a[i] = mod(a[i], n)
  42         a = poly.normalize(a)
  43         return a
  44
  45
  46 # Make a list of all n^d elements of the proposed field.
  47
  48 def make_all(mat):
  49         all = []
  50         for row in mat:
  51                 for a in row:
  52                         all.append(a)
  53         return all
  54
  55 def make_elements(n, d):
  56         if d == 0: return [poly.one(0, 0)]
  57         sub = make_elements(n, d-1)
  58         all = []
  59         for a in sub:
  60                 for i in range(n):
  61                         all.append(poly.plus(a, poly.one(d-1, i)))
  62         return all
  63
  64 def make_inv(all, n, p):
  65         x = poly.one(1, 1)
  66         inv = []
  67         for a in all:
  68                 inv.append(norm(poly.times(a, x), n, p))
  69         return inv
  70
  71 def checkfield(n, p):
  72         all = make_elements(n, len(p)-1)
  73         inv = make_inv(all, n, p)
  74         all1 = all[:]
  75         inv1 = inv[:]
  76         all1.sort()
  77         inv1.sort()
  78         if all1 == inv1: print 'BINGO!'
  79         else:
  80                 print 'Sorry:', n, p
  81                 print all
  82                 print inv
  83
  84 def rj(s, width):
  85         if type(s) <> type(''): s = `s`
  86         n = len(s)
  87         if n >= width: return s
  88         return ' '*(width - n) + s
  89
  90 def lj(s, width):
  91         if type(s) <> type(''): s = `s`
  92         n = len(s)
  93         if n >= width: return s
  94         return s + ' '*(width - n)