|
106
|
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):
|
|
559
|
56 if d == 0: return [poly.one(0, 0)]
|
|
106
|
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()
|
|
559
|
78 if all1 == inv1: print 'BINGO!'
|
|
106
|
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)
|
