Commit | Line | Data |
---|---|---|
920dae64 AT |
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) is not 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) is not type(''): s = `s` | |
92 | n = len(s) | |
93 | if n >= width: return s | |
94 | return s + ' '*(width - n) |