Coverage for /usr/lib/python3/dist-packages/sympy/polys/agca/extensions.py: 29%

1"""Finite extensions of ring domains.""" 

2 

3from sympy.polys.domains.domain import Domain 

4from sympy.polys.domains.domainelement import DomainElement 

5from sympy.polys.polyerrors import (CoercionFailed, NotInvertible, 

6 GeneratorsError) 

7from sympy.polys.polytools import Poly 

8from sympy.printing.defaults import DefaultPrinting 

9 

10 

11class ExtensionElement(DomainElement, DefaultPrinting): 

12 """ 

13 Element of a finite extension. 

14 

15 A class of univariate polynomials modulo the ``modulus`` 

16 of the extension ``ext``. It is represented by the 

17 unique polynomial ``rep`` of lowest degree. Both 

18 ``rep`` and the representation ``mod`` of ``modulus`` 

19 are of class DMP. 

20 

21 """ 

22 __slots__ = ('rep', 'ext') 

23 

24 def __init__(self, rep, ext): 

25 self.rep = rep 

26 self.ext = ext 

27 

28 def parent(f): 

29 return f.ext 

30 

31 def __bool__(f): 

32 return bool(f.rep) 

33 

34 def __pos__(f): 

35 return f 

36 

37 def __neg__(f): 

38 return ExtElem(-f.rep, f.ext) 

39 

40 def _get_rep(f, g): 

41 if isinstance(g, ExtElem): 

42 if g.ext == f.ext: 

43 return g.rep 

44 else: 

45 return None 

46 else: 

47 try: 

48 g = f.ext.convert(g) 

49 return g.rep 

50 except CoercionFailed: 

51 return None 

52 

53 def __add__(f, g): 

54 rep = f._get_rep(g) 

55 if rep is not None: 

56 return ExtElem(f.rep + rep, f.ext) 

57 else: 

58 return NotImplemented 

59 

60 __radd__ = __add__ 

61 

62 def __sub__(f, g): 

63 rep = f._get_rep(g) 

64 if rep is not None: 

65 return ExtElem(f.rep - rep, f.ext) 

66 else: 

67 return NotImplemented 

68 

69 def __rsub__(f, g): 

70 rep = f._get_rep(g) 

71 if rep is not None: 

72 return ExtElem(rep - f.rep, f.ext) 

73 else: 

74 return NotImplemented 

75 

76 def __mul__(f, g): 

77 rep = f._get_rep(g) 

78 if rep is not None: 

79 return ExtElem((f.rep * rep) % f.ext.mod, f.ext) 

80 else: 

81 return NotImplemented 

82 

83 __rmul__ = __mul__ 

84 

85 def _divcheck(f): 

86 """Raise if division is not implemented for this divisor""" 

87 if not f: 

88 raise NotInvertible('Zero divisor') 

89 elif f.ext.is_Field: 

90 return True 

91 elif f.rep.is_ground and f.ext.domain.is_unit(f.rep.rep[0]): 

92 return True 

93 else: 

94 # Some cases like (2*x + 2)/2 over ZZ will fail here. It is 

95 # unclear how to implement division in general if the ground 

96 # domain is not a field so for now it was decided to restrict the 

97 # implementation to division by invertible constants. 

98 msg = (f"Can not invert {f} in {f.ext}. " 

99 "Only division by invertible constants is implemented.") 

100 raise NotImplementedError(msg) 

101 

102 def inverse(f): 

103 """Multiplicative inverse. 

104 

105 Raises 

106 ====== 

107 

108 NotInvertible 

109 If the element is a zero divisor. 

110 

111 """ 

112 f._divcheck() 

113 

114 if f.ext.is_Field: 

115 invrep = f.rep.invert(f.ext.mod) 

116 else: 

117 R = f.ext.ring 

118 invrep = R.exquo(R.one, f.rep) 

119 

120 return ExtElem(invrep, f.ext) 

121 

122 def __truediv__(f, g): 

123 rep = f._get_rep(g) 

124 if rep is None: 

125 return NotImplemented 

126 g = ExtElem(rep, f.ext) 

127 

128 try: 

129 ginv = g.inverse() 

130 except NotInvertible: 

131 raise ZeroDivisionError(f"{f} / {g}") 

132 

133 return f * ginv 

134 

135 __floordiv__ = __truediv__ 

136 

137 def __rtruediv__(f, g): 

138 try: 

139 g = f.ext.convert(g) 

140 except CoercionFailed: 

141 return NotImplemented 

142 return g / f 

143 

144 __rfloordiv__ = __rtruediv__ 

145 

146 def __mod__(f, g): 

147 rep = f._get_rep(g) 

148 if rep is None: 

149 return NotImplemented 

150 g = ExtElem(rep, f.ext) 

151 

152 try: 

153 g._divcheck() 

154 except NotInvertible: 

155 raise ZeroDivisionError(f"{f} % {g}") 

156 

157 # Division where defined is always exact so there is no remainder 

158 return f.ext.zero 

159 

160 def __rmod__(f, g): 

161 try: 

162 g = f.ext.convert(g) 

163 except CoercionFailed: 

164 return NotImplemented 

165 return g % f 

166 

167 def __pow__(f, n): 

168 if not isinstance(n, int): 

169 raise TypeError("exponent of type 'int' expected") 

170 if n < 0: 

171 try: 

172 f, n = f.inverse(), -n 

173 except NotImplementedError: 

174 raise ValueError("negative powers are not defined") 

175 

176 b = f.rep 

177 m = f.ext.mod 

178 r = f.ext.one.rep 

179 while n > 0: 

180 if n % 2: 

181 r = (r*b) % m 

182 b = (b*b) % m 

183 n //= 2 

184 

185 return ExtElem(r, f.ext) 

186 

187 def __eq__(f, g): 

188 if isinstance(g, ExtElem): 

189 return f.rep == g.rep and f.ext == g.ext 

190 else: 

191 return NotImplemented 

192 

193 def __ne__(f, g): 

194 return not f == g 

195 

196 def __hash__(f): 

197 return hash((f.rep, f.ext)) 

198 

199 def __str__(f): 

200 from sympy.printing.str import sstr 

201 return sstr(f.rep) 

202 

203 __repr__ = __str__ 

204 

205 @property 

206 def is_ground(f): 

207 return f.rep.is_ground 

208 

209 def to_ground(f): 

210 [c] = f.rep.to_list() 

211 return c 

212 

213ExtElem = ExtensionElement 

214 

215 

216class MonogenicFiniteExtension(Domain): 

217 r""" 

218 Finite extension generated by an integral element. 

219 

220 The generator is defined by a monic univariate 

221 polynomial derived from the argument ``mod``. 

222 

223 A shorter alias is ``FiniteExtension``. 

224 

225 Examples 

226 ======== 

227 

228 Quadratic integer ring $\mathbb{Z}[\sqrt2]$: 

229 

230 >>> from sympy import Symbol, Poly 

231 >>> from sympy.polys.agca.extensions import FiniteExtension 

232 >>> x = Symbol('x') 

233 >>> R = FiniteExtension(Poly(x**2 - 2)); R 

234 ZZ[x]/(x**2 - 2) 

235 >>> R.rank 

236 2 

237 >>> R(1 + x)*(3 - 2*x) 

238 x - 1 

239 

240 Finite field $GF(5^3)$ defined by the primitive 

241 polynomial $x^3 + x^2 + 2$ (over $\mathbb{Z}_5$). 

242 

243 >>> F = FiniteExtension(Poly(x**3 + x**2 + 2, modulus=5)); F 

244 GF(5)[x]/(x**3 + x**2 + 2) 

245 >>> F.basis 

246 (1, x, x**2) 

247 >>> F(x + 3)/(x**2 + 2) 

248 -2*x**2 + x + 2 

249 

250 Function field of an elliptic curve: 

251 

252 >>> t = Symbol('t') 

253 >>> FiniteExtension(Poly(t**2 - x**3 - x + 1, t, field=True)) 

254 ZZ(x)[t]/(t**2 - x**3 - x + 1) 

255 

256 """ 

257 is_FiniteExtension = True 

258 

259 dtype = ExtensionElement 

260 

261 def __init__(self, mod): 

262 if not (isinstance(mod, Poly) and mod.is_univariate): 

263 raise TypeError("modulus must be a univariate Poly") 

264 

265 # Using auto=True (default) potentially changes the ground domain to a 

266 # field whereas auto=False raises if division is not exact. We'll let 

267 # the caller decide whether or not they want to put the ground domain 

268 # over a field. In most uses mod is already monic. 

269 mod = mod.monic(auto=False) 

270 

271 self.rank = mod.degree() 

272 self.modulus = mod 

273 self.mod = mod.rep # DMP representation 

274 

275 self.domain = dom = mod.domain 

276 self.ring = mod.rep.ring or dom.old_poly_ring(*mod.gens) 

277 

278 self.zero = self.convert(self.ring.zero) 

279 self.one = self.convert(self.ring.one) 

280 

281 gen = self.ring.gens[0] 

282 self.symbol = self.ring.symbols[0] 

283 self.generator = self.convert(gen) 

284 self.basis = tuple(self.convert(gen**i) for i in range(self.rank)) 

285 

286 # XXX: It might be necessary to check mod.is_irreducible here 

287 self.is_Field = self.domain.is_Field 

288 

289 def new(self, arg): 

290 rep = self.ring.convert(arg) 

291 return ExtElem(rep % self.mod, self) 

292 

293 def __eq__(self, other): 

294 if not isinstance(other, FiniteExtension): 

295 return False 

296 return self.modulus == other.modulus 

297 

298 def __hash__(self): 

299 return hash((self.__class__.__name__, self.modulus)) 

300 

301 def __str__(self): 

302 return "%s/(%s)" % (self.ring, self.modulus.as_expr()) 

303 

304 __repr__ = __str__ 

305 

306 def convert(self, f, base=None): 

307 rep = self.ring.convert(f, base) 

308 return ExtElem(rep % self.mod, self) 

309 

310 def convert_from(self, f, base): 

311 rep = self.ring.convert(f, base) 

312 return ExtElem(rep % self.mod, self) 

313 

314 def to_sympy(self, f): 

315 return self.ring.to_sympy(f.rep) 

316 

317 def from_sympy(self, f): 

318 return self.convert(f) 

319 

320 def set_domain(self, K): 

321 mod = self.modulus.set_domain(K) 

322 return self.__class__(mod) 

323 

324 def drop(self, *symbols): 

325 if self.symbol in symbols: 

326 raise GeneratorsError('Can not drop generator from FiniteExtension') 

327 K = self.domain.drop(*symbols) 

328 return self.set_domain(K) 

329 

330 def quo(self, f, g): 

331 return self.exquo(f, g) 

332 

333 def exquo(self, f, g): 

334 rep = self.ring.exquo(f.rep, g.rep) 

335 return ExtElem(rep % self.mod, self) 

336 

337 def is_negative(self, a): 

338 return False 

339 

340 def is_unit(self, a): 

341 if self.is_Field: 

342 return bool(a) 

343 elif a.is_ground: 

344 return self.domain.is_unit(a.to_ground()) 

345 

346FiniteExtension = MonogenicFiniteExtension