Repository: sympy/sympy
Pull request: fix(polys): fix DMP.cancel for GF(p) with Flint
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->

Fixes gh-26804

#### Brief description of what is fixed or changed


#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers. Formerly, `log(-x)` incorrectly gave `-log(x)`.

* physics.units
  * Corrected a semantical error in the conversion between volt and statvolt which
    reported the volt as being larger than the statvolt.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
NO ENTRY
<!-- END RELEASE NOTES -->


Problem statement:
Poly.cancel fails over GF with ground types flint
This is after gh-25940
```python
In [1]: Poly(x, modulus=11).cancel(Poly(x, modulus=11))
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[1], line 1
----> 1 Poly(x, modulus=11).cancel(Poly(x, modulus=11))

File ~/current/active/sympy/sympy/polys/polytools.py:3890, in Poly.cancel(f, g, include)
   3887 dom, per, F, G = f._unify(g)
   3889 if hasattr(F, 'cancel'):
-> 3890     result = F.cancel(G, include=include)
   3891 else:  # pragma: no cover
   3892     raise OperationNotSupported(f, 'cancel')

File ~/current/active/sympy/sympy/polys/polyclasses.py:849, in DMP.cancel(f, g, include)
    847     return F._cancel_include(G)
    848 else:
--> 849     return F._cancel(G)

File ~/current/active/sympy/sympy/polys/polyclasses.py:2143, in DUP_Flint._cancel(f, g)
   2140 """Cancel common factors in a rational function ``f/g``. """
   2141 # Think carefully about how to handle denominators and coefficient
   2142 # canonicalisation if more domains are permitted...
-> 2143 assert f.dom == g.dom in (ZZ, QQ)
   2145 if f.dom.is_QQ:
   2146     cG, F = f.clear_denoms()

AssertionError: 
```

Hints from issue discussion:

Commit message: fix(polys): fix DMP.cancel for GF(p) with Flint

Patch to review:
diff --git a/sympy/polys/polyclasses.py b/sympy/polys/polyclasses.py
index 55780f086709..eab3b39034a7 100644
--- a/sympy/polys/polyclasses.py
+++ b/sympy/polys/polyclasses.py
@@ -2138,19 +2138,28 @@ def _lcm(f, g):
 
     def _cancel(f, g):
         """Cancel common factors in a rational function ``f/g``. """
+        assert f.dom == g.dom
+        R = f.dom
+
         # Think carefully about how to handle denominators and coefficient
         # canonicalisation if more domains are permitted...
-        assert f.dom == g.dom in (ZZ, QQ)
+        assert R.is_ZZ or R.is_QQ or R.is_FiniteField
 
-        if f.dom.is_QQ:
+        if R.is_FiniteField:
+            h = f._gcd(g)
+            F, G = f.exquo(h), g.exquo(h)
+            return R.one, R.one, F, G
+
+        if R.is_QQ:
             cG, F = f.clear_denoms()
             cF, G = g.clear_denoms()
         else:
-            cG, F = f.dom.one, f
-            cF, G = g.dom.one, g
+            cG, F = R.one, f
+            cF, G = R.one, g
 
-        cH = cF.gcd(cG)
-        cF, cG = cF // cH, cG // cH
+        if R.is_ZZ or R.is_QQ:
+            cH = cF.gcd(cG)
+            cF, cG = cF // cH, cG // cH
 
         H = F._gcd(G)
         F, G = F.exquo(H), G.exquo(H)
diff --git a/sympy/polys/tests/test_polytools.py b/sympy/polys/tests/test_polytools.py
index 28ece86006aa..be81aac66a5e 100644
--- a/sympy/polys/tests/test_polytools.py
+++ b/sympy/polys/tests/test_polytools.py
@@ -3405,6 +3405,12 @@ def test_cancel():
     assert cancel((x**2 + 1)/(x - I)) == x + I
 
 
+def test_cancel_modulus():
+    assert cancel((x**2 - 1)/(x + 1), modulus=2) == x + 1
+    assert Poly(x**2 - 1, modulus=2).cancel(Poly(x + 1, modulus=2)) ==\
+            (1, Poly(x + 1, modulus=2), Poly(1, x, modulus=2))
+
+
 def test_make_monic_over_integers_by_scaling_roots():
     f = Poly(x**2 + 3*x + 4, x, domain='ZZ')
     g, c = f.make_monic_over_integers_by_scaling_roots()


Code review comments:
diff_hunk: @@ -2138,19 +2138,28 @@ def _lcm(f, g):
 
     def _cancel(f, g):
         """Cancel common factors in a rational function ``f/g``. """
+        assert f.dom == g.dom
+        R = f.dom
+
         # Think carefully about how to handle denominators and coefficient
         # canonicalisation if more domains are permitted...
-        assert f.dom == g.dom in (ZZ, QQ)
+        assert R.is_ZZ or R.is_QQ or R.is_FiniteField
 
-        if f.dom.is_QQ:
+        if R.is_FiniteField:
+            h = f._gcd(g)
+            F, G = f.exquo(h), g.exquo(h)
+            return R.one, R.one, F, G
+
+        if R.is_QQ:
             cG, F = f.clear_denoms()
             cF, G = g.clear_denoms()
         else:
-            cG, F = f.dom.one, f
-            cF, G = g.dom.one, g
+            cG, F = R.one, f
+            cF, G = R.one, g
 
-        cH = cF.gcd(cG)
-        cF, cG = cF // cH, cG // cH
+        if R.is_ZZ or R.is_QQ:
path: sympy/polys/polyclasses.py
text: @user1:
Is it necessary to check `is_ZZ or is_QQ` here? `is_FiniteField` is narrowed down from above

@author:
Oh, good point