Opened 13 years ago

Closed 13 years ago

# [with patch, with positive review] factoring integer polynomials does not factor the content

Reported by: Owned by: cremona tbd major sage-3.4.2 algebra

### 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.

### 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: ↓ 11 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

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
(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.

### 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.