-
Notifications
You must be signed in to change notification settings - Fork 4
/
galois.py
executable file
·189 lines (164 loc) · 4.96 KB
/
galois.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#!/usr/bin/env python
import itertools
class GF():
def __init__(self, p, m, px=None):
self.p = p
self.m = m
if px:
assert len(px) == self.m + 1
F = GF(self.p, self.m + 1)
self.px = Poly(F, px)
else:
self.px = None
def list(self):
perms = list(itertools.product(range(self.p), repeat=self.m))
for perm in perms:
yield Poly(self, perm)
def __eq__(self, other):
return self.p == other.p and self.m == other.m
def __lt__(self, other):
return self.p == other.p and self.m < other.m
def __gt__(self, other):
return self.p == other.p and self.m > other.m
def __str__(self):
if self.px:
return 'GF(%d^%d) [%s]' % (self.p, self.m, self.px)
else:
return 'GF(%d^%d)' % (self.p, self.m)
class Poly():
def __init__(self, *args, **kwargs):
self.gf = args[0]
if len(args[1:]) == 1:
vec = args[1]
else:
vec = args[1:]
assert len(vec) <= self.gf.m
if len(vec) < self.gf.m:
pad = [0] * (self.gf.m - len(vec))
vec = tuple(pad) + tuple(vec)
self.vec = vec
def __add__(self, p2):
assert self.gf.p == p2.gf.p
if self.gf > p2.gf:
p2 = p2.expand(self.gf)
elif self.gf < p2.gf:
self = self.expand(p2.gf)
rv = []
for a, b in zip(self.vec, p2.vec):
alpha = (a + b) % self.gf.p
rv.append(alpha)
return Poly(self.gf, tuple(rv))
def __sub__(self, p2):
if self.gf.p == 2:
return self.__add__(p2)
else:
assert self.gf == p2.gf
rv = []
for a, b in zip(self.vec, p2.vec):
alpha = (a - b) % self.gf.p
rv.append(alpha)
return Poly(self.gf, tuple(rv))
def __pmul(self, p2):
assert self.gf == p2.gf
l = len(self.vec)
# Mul two tuples mod P(x)
res = [0] * l**2
for pos1, i1 in enumerate(self.vec):
for pos2, i2 in enumerate(p2.vec):
val = (i1 * i2) % self.gf.p
pos = (l-pos1-1) + (l-pos2-1)
res[pos] += val
res[pos] %= self.gf.p
return Poly(GF(self.gf.p, l**2), res[::-1]).compress()
def __mul__(self, p2):
r = self.__pmul(p2)
return r % self.gf.px
def __mod__(self, p2):
red = Poly(self.gf, self.vec)
div = Poly(p2.gf, (0, 0))
p2 = p2.expand(self.gf)
l = self.gf.m
for _ in range(2):
red = red.expand(p2.gf)
res = [0] * l
for pos1, i1 in enumerate(red.vec):
if i1 == 1:
msb1 = l-pos1
break
for pos2, i2 in enumerate(p2.vec):
if i2 == 1:
msb2 = l-pos2
break
pos = msb1 - msb2
res[l-pos-1] = 1
ii = Poly(self.gf, res)
div += ii
red += ii.__pmul(p2)
red = red.compress()
if red.gf < p2.compress().gf:
break
return red
def __str__(self):
s = ''
j = 1
zero = True
for i in self.vec:
if i > 0:
zero = False
p = self.gf.m - j
if p == 0:
s += '%d + ' % i
elif p == 1:
if i > 1:
s += '%dx + ' % i
else:
s += 'x + '
else:
if i > 1:
s += '%dx^%d + ' % (i, p)
else:
s += 'x^%d + ' % p
j += 1
if zero:
s += "0 "
return "%s in %s" % (s[:-3], self.gf)
def expand(self, gf):
if self.gf < gf:
return Poly(gf, self.vec)
else:
return self
def compress(self):
switch = False
r = []
for _ in self.vec:
if not switch:
switch = _ == 1
if switch:
r.append(_)
return Poly(GF(self.gf.p, len(r)), r)
# F = GF(3, 5)
# print Poly(F, 1, 0, 0, 1, 0)
# print Poly(F, 1, 1, 1, 1, 0)
# print Poly(F, 1, 0, 1, 0, 1)
# print Poly(F, 0, 0, 1, 1, 0)
F = GF(2, 3, (1, 0, 1, 1))
for _ in GF(2, 3).list():
print _
print "====="
# print Poly(F, 0, 1, 0)
# print Poly(F, 1, 1, 1)
# print Poly(F, 1, 0, 1)
# print Poly(F, 1, 1, 0)
print "\n(x^2 + x) + (x^2 + 1)"
print Poly(F, (1, 1, 0)) + Poly(F, (1, 0, 1))
print "\n(x^2 + x) - (x^2 + 1)"
print Poly(F, (1, 1, 0)) - Poly(F, (1, 0, 1))
print "\n(x^2 + x + 1) * (x^2 + 1)"
print Poly(F, (1, 1, 1)) * Poly(F, (1, 0, 1))
# GF(3^3)
print ""
F3 = GF(3, 3, (2, 1, 0, 1))
print F3
print Poly(F3, (1, 2, 0)) + Poly(F3, (1, 0, 2))
# print "\n(x^2 + x) - (x^2 + 1)"
# print Poly(F, (1, 1, 0)) - Poly(F, (1, 0, 1))