/
extensions.py
356 lines (272 loc) · 9.17 KB
/
extensions.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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
"""Finite extensions of ring domains."""
from sympy.polys.domains.domain import Domain
from sympy.polys.domains.domainelement import DomainElement
from sympy.polys.polyerrors import (CoercionFailed, NotInvertible,
GeneratorsError)
from sympy.polys.polytools import Poly
from sympy.printing.defaults import DefaultPrinting
class ExtensionElement(DomainElement, DefaultPrinting):
"""
Element of a finite extension.
A class of univariate polynomials modulo the ``modulus``
of the extension ``ext``. It is represented by the
unique polynomial ``rep`` of lowest degree. Both
``rep`` and the representation ``mod`` of ``modulus``
are of class DMP.
"""
__slots__ = ('rep', 'ext')
def __init__(self, rep, ext):
self.rep = rep
self.ext = ext
def parent(f):
return f.ext
def as_expr(f):
return f.ext.to_sympy(f)
def __bool__(f):
return bool(f.rep)
def __pos__(f):
return f
def __neg__(f):
return ExtElem(-f.rep, f.ext)
def _get_rep(f, g):
if isinstance(g, ExtElem):
if g.ext == f.ext:
return g.rep
else:
return None
else:
try:
g = f.ext.convert(g)
return g.rep
except CoercionFailed:
return None
def __add__(f, g):
rep = f._get_rep(g)
if rep is not None:
return ExtElem(f.rep + rep, f.ext)
else:
return NotImplemented
__radd__ = __add__
def __sub__(f, g):
rep = f._get_rep(g)
if rep is not None:
return ExtElem(f.rep - rep, f.ext)
else:
return NotImplemented
def __rsub__(f, g):
rep = f._get_rep(g)
if rep is not None:
return ExtElem(rep - f.rep, f.ext)
else:
return NotImplemented
def __mul__(f, g):
rep = f._get_rep(g)
if rep is not None:
return ExtElem((f.rep * rep) % f.ext.mod, f.ext)
else:
return NotImplemented
__rmul__ = __mul__
def _divcheck(f):
"""Raise if division is not implemented for this divisor"""
if not f:
raise NotInvertible('Zero divisor')
elif f.ext.is_Field:
return True
elif f.rep.is_ground and f.ext.domain.is_unit(f.rep.LC()):
return True
else:
# Some cases like (2*x + 2)/2 over ZZ will fail here. It is
# unclear how to implement division in general if the ground
# domain is not a field so for now it was decided to restrict the
# implementation to division by invertible constants.
msg = (f"Can not invert {f} in {f.ext}. "
"Only division by invertible constants is implemented.")
raise NotImplementedError(msg)
def inverse(f):
"""Multiplicative inverse.
Raises
======
NotInvertible
If the element is a zero divisor.
"""
f._divcheck()
if f.ext.is_Field:
invrep = f.rep.invert(f.ext.mod)
else:
R = f.ext.ring
invrep = R.exquo(R.one, f.rep)
return ExtElem(invrep, f.ext)
def __truediv__(f, g):
rep = f._get_rep(g)
if rep is None:
return NotImplemented
g = ExtElem(rep, f.ext)
try:
ginv = g.inverse()
except NotInvertible:
raise ZeroDivisionError(f"{f} / {g}")
return f * ginv
__floordiv__ = __truediv__
def __rtruediv__(f, g):
try:
g = f.ext.convert(g)
except CoercionFailed:
return NotImplemented
return g / f
__rfloordiv__ = __rtruediv__
def __mod__(f, g):
rep = f._get_rep(g)
if rep is None:
return NotImplemented
g = ExtElem(rep, f.ext)
try:
g._divcheck()
except NotInvertible:
raise ZeroDivisionError(f"{f} % {g}")
# Division where defined is always exact so there is no remainder
return f.ext.zero
def __rmod__(f, g):
try:
g = f.ext.convert(g)
except CoercionFailed:
return NotImplemented
return g % f
def __pow__(f, n):
if not isinstance(n, int):
raise TypeError("exponent of type 'int' expected")
if n < 0:
try:
f, n = f.inverse(), -n
except NotImplementedError:
raise ValueError("negative powers are not defined")
b = f.rep
m = f.ext.mod
r = f.ext.one.rep
while n > 0:
if n % 2:
r = (r*b) % m
b = (b*b) % m
n //= 2
return ExtElem(r, f.ext)
def __eq__(f, g):
if isinstance(g, ExtElem):
return f.rep == g.rep and f.ext == g.ext
else:
return NotImplemented
def __ne__(f, g):
return not f == g
def __hash__(f):
return hash((f.rep, f.ext))
def __str__(f):
from sympy.printing.str import sstr
return sstr(f.as_expr())
__repr__ = __str__
@property
def is_ground(f):
return f.rep.is_ground
def to_ground(f):
[c] = f.rep.to_list()
return c
ExtElem = ExtensionElement
class MonogenicFiniteExtension(Domain):
r"""
Finite extension generated by an integral element.
The generator is defined by a monic univariate
polynomial derived from the argument ``mod``.
A shorter alias is ``FiniteExtension``.
Examples
========
Quadratic integer ring $\mathbb{Z}[\sqrt2]$:
>>> from sympy import Symbol, Poly
>>> from sympy.polys.agca.extensions import FiniteExtension
>>> x = Symbol('x')
>>> R = FiniteExtension(Poly(x**2 - 2)); R
ZZ[x]/(x**2 - 2)
>>> R.rank
2
>>> R(1 + x)*(3 - 2*x)
x - 1
Finite field $GF(5^3)$ defined by the primitive
polynomial $x^3 + x^2 + 2$ (over $\mathbb{Z}_5$).
>>> F = FiniteExtension(Poly(x**3 + x**2 + 2, modulus=5)); F
GF(5)[x]/(x**3 + x**2 + 2)
>>> F.basis
(1, x, x**2)
>>> F(x + 3)/(x**2 + 2)
-2*x**2 + x + 2
Function field of an elliptic curve:
>>> t = Symbol('t')
>>> FiniteExtension(Poly(t**2 - x**3 - x + 1, t, field=True))
ZZ(x)[t]/(t**2 - x**3 - x + 1)
"""
is_FiniteExtension = True
dtype = ExtensionElement
def __init__(self, mod):
if not (isinstance(mod, Poly) and mod.is_univariate):
raise TypeError("modulus must be a univariate Poly")
# Using auto=True (default) potentially changes the ground domain to a
# field whereas auto=False raises if division is not exact. We'll let
# the caller decide whether or not they want to put the ground domain
# over a field. In most uses mod is already monic.
mod = mod.monic(auto=False)
self.rank = mod.degree()
self.modulus = mod
self.mod = mod.rep # DMP representation
self.domain = dom = mod.domain
self.ring = dom.old_poly_ring(*mod.gens)
self.zero = self.convert(self.ring.zero)
self.one = self.convert(self.ring.one)
gen = self.ring.gens[0]
self.symbol = self.ring.symbols[0]
self.generator = self.convert(gen)
self.basis = tuple(self.convert(gen**i) for i in range(self.rank))
# XXX: It might be necessary to check mod.is_irreducible here
self.is_Field = self.domain.is_Field
def new(self, arg):
rep = self.ring.convert(arg)
return ExtElem(rep % self.mod, self)
def __eq__(self, other):
if not isinstance(other, FiniteExtension):
return False
return self.modulus == other.modulus
def __hash__(self):
return hash((self.__class__.__name__, self.modulus))
def __str__(self):
return "%s/(%s)" % (self.ring, self.modulus.as_expr())
__repr__ = __str__
@property
def has_CharacteristicZero(self):
return self.domain.has_CharacteristicZero
def characteristic(self):
return self.domain.characteristic()
def convert(self, f, base=None):
rep = self.ring.convert(f, base)
return ExtElem(rep % self.mod, self)
def convert_from(self, f, base):
rep = self.ring.convert(f, base)
return ExtElem(rep % self.mod, self)
def to_sympy(self, f):
return self.ring.to_sympy(f.rep)
def from_sympy(self, f):
return self.convert(f)
def set_domain(self, K):
mod = self.modulus.set_domain(K)
return self.__class__(mod)
def drop(self, *symbols):
if self.symbol in symbols:
raise GeneratorsError('Can not drop generator from FiniteExtension')
K = self.domain.drop(*symbols)
return self.set_domain(K)
def quo(self, f, g):
return self.exquo(f, g)
def exquo(self, f, g):
rep = self.ring.exquo(f.rep, g.rep)
return ExtElem(rep % self.mod, self)
def is_negative(self, a):
return False
def is_unit(self, a):
if self.is_Field:
return bool(a)
elif a.is_ground:
return self.domain.is_unit(a.to_ground())
FiniteExtension = MonogenicFiniteExtension