blob: 4f03626390390d907dbb2cd00cc295b7a92ac2f8 [file] [log] [blame]
Guido van Rossum762c39e1991-01-01 18:11:14 +00001# 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
21import poly
22
23
24# Example N and polynomial
25
26N = 5
27P = 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
32def mod(x, y):
33 return divmod(x, y)[1]
34
35
36# Normalize a polynomial modulo n and modulo p.
37
38def 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
48def make_all(mat):
49 all = []
50 for row in mat:
51 for a in row:
52 all.append(a)
53 return all
54
55def make_elements(n, d):
Guido van Rossumbdfcfcc1992-01-01 19:35:13 +000056 if d == 0: return [poly.one(0, 0)]
Guido van Rossum762c39e1991-01-01 18:11:14 +000057 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
64def 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
71def 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()
Guido van Rossumbdfcfcc1992-01-01 19:35:13 +000078 if all1 == inv1: print 'BINGO!'
Guido van Rossum762c39e1991-01-01 18:11:14 +000079 else:
80 print 'Sorry:', n, p
81 print all
82 print inv
83
84def 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
90def 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)