Opened 13 years ago
Closed 13 years ago
#5921 closed defect (fixed)
[with patch, with positive review] factoring integer polynomials does not factor the content
Reported by: | cremona | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-3.4.2 |
Component: | algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
I think this is wrong:
sage: R.<x> = ZZ[] sage: f = 30*x sage: f.factor() 30 * x
since in the ring ZZ[] 30 is not irreducible; it should return 2*3*5*x.
Attachments (2)
Change History (16)
Changed 13 years ago by
comment:1 Changed 13 years ago by
- Summary changed from factoring integer polynomials does not factor the content to [with patch, needs review] factoring integer polynomials does not factor the content
comment:2 Changed 13 years ago by
comment:3 Changed 13 years ago by
OK, I've found a very simple example where this bombs:
sage: P.<x> = ZZ[] sage: f = 2*x + 2 sage: f.roots() ... NotImplementedError:
comment:4 Changed 13 years ago by
Hmmm. We just had this situation happen on a different ticket: the code in this patch is fine but breaks something, which really exposes a pre-existing bug.
In this case, John's code factors the content and the "normalised, content-free" polynomial separately and multiplies the two factorisations. The problem is the with the types: the first factorisation consists of integers, while the second one consists of polynomials. Multiplying them together yields a factorisation where some factors are of type integer and the others of type polynomial, and then this breaks all sorts of things later on.
I've made a new ticket at #5928 and will have a patch up there soon. Then John's patch on this ticket will be good to go.
comment:5 Changed 13 years ago by
There's now a patch up at #5928. I've tested again with John's patch applied and the polynomial_zmod_flint.pyx
problems are gone, but I'm still getting timeouts in polynomial_modn_dense_ntl.pyx
. So there's more to this than I thought.
comment:6 Changed 13 years ago by
Yes, the problem is in f.roots()
for a polynomial f with integer coefficients. The code used to just run f.factor()
, but of course now if the content is a huge integer it's gonna take a while for the factoring to finish. There's a doctest in the sage library that runs into precisely this problem now, since it's an illustration of RSA and has huge coefficients (and a huge content) floating around. However, you don't care about the content if you just want the roots of the polynomial.
So the attached patch makes roots()
divide by the content first, then call factor()
. It also adds a warning to this effect in the docstrings of the two factor()
methods.
I'm happy with John's patch, so if someone reviews my patch we're done.
comment:7 Changed 13 years ago by
I forgot to mention this again: this ticket depends on the patch at #5928, so that should be applied first.
comment:8 Changed 13 years ago by
I am happy with Alex's patch. I made mine a bit too quickly or I would have thought about the universes being different. So I will give this a positive review as soon as I have gone to look at #5928.
comment:9 Changed 13 years ago by
- Summary changed from [with patch, needs review] factoring integer polynomials does not factor the content to [with patch, with positive review] factoring integer polynomials does not factor the content
I applied both patches after #5928 on top of 3.4.2.alpha0, fine. Ran all tests in sage/rings/polynomial (all fine) and sage/rings/number_field (all fine).
So I have given this a positive review since Alex and I have reviewed eachothers' patches.
comment:10 follow-up: ↓ 11 Changed 13 years ago by
- Summary changed from [with patch, with positive review] factoring integer polynomials does not factor the content to [with patch, needs work] factoring integer polynomials does not factor the content
These two patches break
sage -t -long devel/sage/sage/modular/overconvergent/genus0.py
Cheers,
Michael
comment:11 in reply to: ↑ 10 Changed 13 years ago by
Replying to mabshoff:
These two patches break
sage -t -long devel/sage/sage/modular/overconvergent/genus0.py
This is due to a bug in p-adics, more precisely in the content method for p-adic polynomials:
sage: P.<x> = ZZ[] sage: f = x + 2 sage: f.content() 1 sage: fp = f.change_ring(pAdicField(2, 10)) sage: fp (1 + O(2^10))*x + (2 + O(2^11)) sage: fp.content() 0
I have checked and the monster p-adic patch bomb at #5778 doesn't help with this. I'll see what we can do.
comment:12 Changed 13 years ago by
- Summary changed from [with patch, needs work] factoring integer polynomials does not factor the content to [with patch, needs review] factoring integer polynomials does not factor the content
OK, I've made a simple modification in my patch that sidesteps the p-adic polynomial bug (for which there is now a new trac ticket #5946).
I have replaced my patch with the new version, so one still needs to apply both patches.
Changed 13 years ago by
comment:13 Changed 13 years ago by
- Summary changed from [with patch, needs review] factoring integer polynomials does not factor the content to [with patch, with positive review] factoring integer polynomials does not factor the content
With Alex's new patch (on top of mine all tests in modular/overconvergent/* pass as well as all in rings/polynomial
I reinstated Positive Review and am keeping my fingers crossed!
comment:14 Changed 13 years ago by
- Milestone changed from sage-4.0 to sage-3.4.2
- Resolution set to fixed
- Status changed from new to closed
Merged both patches in Sage 3.4.2.rc0.
Cheers,
Michael
Hi John,
The changes in the patch look fine, but for some reason they make doctests fail in two places:
polynomial_zmod_flint.pyx
(with some errors) andpolynomial_modn_dense_ntl.pyx
(killed after timeout). I'm rushing to teach right now, but I'll try to investigate afterward.