# PolyDiv

## 1957 days ago by donvel

P1.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
F = [x - y^2, y - z^3, z^2 - 1]
f = x*y^2*z^2 + x*y - y*z
f.reduce(F[1:] + F[:1])
 `z`
f.reduce(list(reversed(F)))
 `z`
f.reduce(F)
 `z`

 `[y - z^3, z^2 - 1, x - y^2]`
P2.<x1,y1,z1> = PolynomialRing(QQ, 3, order='deglex')
F2 = [x1 - y1^2, y1 - z1^3, z1^2 - 1]
f2 = x1*y1^2*z1^2 + x1*y1 - y1*z1
f2.reduce(F2)
 `x1^2 + x1*y1 - y1*z1`
f2.reduce(list(reversed(F2)))
 `x1^2 + x1*y1 - y1*z1`
f2.reduce(F2[1:] + F2[:1])
 `x1^2 + x1*y1 - y1*z1`
F.<x,y> = PolynomialRing(QQ, 2, order='lex')
f1 = x * y + 1
f2 = y^2 - 1
f = x * y^2 - x
f.reduce([f1, f2]) # EH :(
 `0`
f.reduce([f2, f1])
 `0`

g = x * y + 1
g + x
 `x*y + x + 1`
g += x
 `x*y + x + 1`
g.lt()
 `x*y`
g.lt().divides((x*y).lt())
 `True`
def polydiv(F, f): # Cox, Little, OShea, p. 64 p = f r = 0 a = [0] * len(F) while p != 0: docc = False i = 0 while i < len(F) and not docc: ltf = F[i].lt() ltp = p.lt() if ltf.divides(ltp): q = ltp.quo_rem(ltf)[0] a[i] += q p -= q * F[i] docc = True else: i += 1 if not docc: r += p.lt() p -= p.lt() return a, r
polydiv([f1, f2], f)
 `([y, 0], -x - y)`
polydiv(F, f)
 ```([y^2*z^2 + y, y^3*z^2 + y^2*z^5 + y^2 + y*z^8 + y*z^3 + z^11 + z^6 - z, z^12 + z^10 + z^8 + z^7 + z^6 + z^5 + z^4 + z^3 + z], z)```
polydiv(list(reversed(F)), f)
 ```([x*y^2 + x*y*z + x*z^2 + x*z + x + y*z^2 + y*z + y + z, x*y + x*z + x + y*z + y + 1, z + 1], z)```
polydiv(F2, f2)
 `([-x1*z1^2, 0, x1^2], x1^2 + x1*y1 - y1*z1)`
polydiv(list(reversed(F2)), f2)
 `([x1*y1^2, 0, -x1], x1^2 + x1*y1 - y1*z1)`
polydiv(F[1:] + F[:1], f)
 ```([x*y*z^2 + x*z^5 + x + y*z + y + z^4 + z^3 - z, x*z^6 + x*z^4 + x*z^2 + x*z + x + z^5 + z^4 + z^3 + z, z + 1], z)```
polydiv(F2[1:] + F2[:1], f2)
 `([0, x1*y1^2, -x1], x1^2 + x1*y1 - y1*z1)`