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:

Status badges

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)

trac_5921.patch (2.1 KB) - added by cremona 13 years ago.
trac_5921_fix.patch (2.5 KB) - added by AlexGhitza 13 years ago.

Download all attachments as: .zip

Change History (16)

Changed 13 years ago by cremona

comment:1 Changed 13 years ago by cremona

  • 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 AlexGhitza

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) and polynomial_modn_dense_ntl.pyx (killed after timeout). I'm rushing to teach right now, but I'll try to investigate afterward.

comment:3 Changed 13 years ago by AlexGhitza

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 AlexGhitza

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 AlexGhitza

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 AlexGhitza

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 AlexGhitza

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 cremona

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 cremona

  • 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: Changed 13 years ago by mabshoff

  • 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 AlexGhitza

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 AlexGhitza

  • 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 AlexGhitza

comment:13 Changed 13 years ago by cremona

  • 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 mabshoff

  • 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

Note: See TracTickets for help on using tickets.