Opened 10 years ago

Closed 10 years ago

# Sage cannot factor polynomials over number fields with unfactorable discriminant

Reported by: Owned by: jdemeyer davidloeffler major sage-4.8 number fields nffactor PARI nfinit pari_nf sage-4.8.alpha1 Jeroen Demeyer Luis Felipe Tabera Alonso N/A #11891, #11130

Let `K` be a number field with a discriminant which cannot be factored. Let `f` be a polynomial in `K[x]`. Then Sage is unable to factor `f` because it calls PARI's `nfinit()` on `K`:

```sage: p = next_prime(10^50); q = next_prime(10^51)
sage: x = polygen(K); factor(x^2+1)
[... takes a very long time ...]
```

The solution is to call `nfinit()` with the defining polynomial when the discriminant cannot be factored. If that fails, fall back to `factornf()`.

### comment:1 Changed 10 years ago by jdemeyer

• Description modified (diff)

### comment:2 Changed 10 years ago by jdemeyer

• Authors set to Jeroen Demeyer
• Dependencies set to #11891
• Milestone changed from sage-4.7.2 to sage-4.7.3

### comment:3 Changed 10 years ago by jdemeyer

• Description modified (diff)
• Status changed from new to needs_review

### comment:4 Changed 10 years ago by jdemeyer

• Dependencies changed from #11891 to #11891, #11130

### comment:5 follow-up: ↓ 6 Changed 10 years ago by lftabera

Jeroen,

This ticket is a duplicate of #10910

In that ticket I presented another approach. I still use nffactor but do not use nfinit UNLESS nfinit has already been computed and cached. A couple of comments regarding both approaches:

• Now we do not need nfinit for nffactor. So we can use either nffactor or factornf at will.
• In most cases nffactor will be faster than factornf (I should give numbers to sustain that though).
• My patch also work for non-integral generators.
• But my patch fails in your example with a PariError? exception: precision too low.

I have to investigate this error. It might be a Pari bug or there are instances where we really need factornf.

### comment:6 in reply to: ↑ 5 Changed 10 years ago by jdemeyer

• But my patch fails in your example with a PariError? exception: precision too low.

This is exactly the reason why I am using `factornf` instead of `nffactor`: `nffactor` somehow computes a partial `nfinit` structure which does some floating-point stuff. Apparently, the floating-point precision is not sufficient in the example.

### comment:7 follow-up: ↓ 8 Changed 10 years ago by lftabera

Then, we need to be smarter. My experience tells that when nffactor is slower than factornf is for a small relative amount while the other way around is false.

Doing a couple of examples suggest that the PariError? appears quite soon.

```sage: K=NumberField(x^20+ZZ[x].random_element(19,10**20),'a')[x]
sage: f=K.random_element(50)
sage: g=K.random_element(50)
sage: F=f*g
```

In the above exameple, with my patch, the PariError? appears after 6 s. I have not yet computed the factorization of the polynomial with factornf but I claim that it will be quite hard to compute. Pari will use Trager's trick, that means that it will perform gcd's of polynomials in K. And Pari is not very good at it, cf. #8558

We need to figure out which method use, one option is the following:

• If nfinit structure is already known, use (or try) nfffactor(nfinit,f)
• If nfinit is not computed, try nffactor
• If the above fails, use factornf.

Another alternative is to use one algorithm or the other depending on the discriminant of the field if that is the relevant data for the PariError?.

We may even consider implementing our own Trager's ticket (but that should be in another ticket, after #8558 is merged).

I am not yet sure what is the best way to proceed. I also feel that there should be a way for allowing the user to override the algorithm to use. But factor does not allow optional arguments and I do not want to mess the rest of univariate rings.

### comment:8 in reply to: ↑ 7 Changed 10 years ago by jdemeyer

• Status changed from needs_review to needs_work

We need to figure out which method use, one option is the following:

• If nfinit structure is already known, use (or try) nfffactor(nfinit,f)
• If nfinit is not computed, try nffactor
• If the above fails, use factornf.

Agreed. Except that we really should do `nfinit()` if the discriminant is easy.

I am not yet sure what is the best way to proceed. I also feel that there should be a way for allowing the user to override the algorithm to use.

Why? If one algorithm is clearly better than another, why complicate things with extra arguments?

### comment:9 Changed 10 years ago by jdemeyer

• Description modified (diff)
• Status changed from needs_work to needs_review

### comment:10 Changed 10 years ago by lftabera

• Description modified (diff)
• Reviewers set to Luis Felipe Tabera Alonso

The solution here to test the use of nffactor is more elegant than in #10910 and with these patches there are no known failing cases. All doctest pases on sage-4.7.2-alpha3 + #11130 + #11891

I give a positive review to Jeroen's patches but I add a patch that needs review with a couple of things:

-On a complicated case we show that the discriminant is not fully factored by trial division.

-The second example is a test case that shows that we really need the new version of Pari in #11130 this case will fail with older versions of Pari (See Pari bug pari bug #1207)

### comment:11 Changed 10 years ago by jdemeyer

• Status changed from needs_review to positive_review

Reviewer patch looks good to me. Thanks!

For those interested: the PARI bug is http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1207

### comment:12 Changed 10 years ago by jdemeyer

• Milestone changed from sage-4.7.3 to sage-pending

### comment:13 Changed 10 years ago by jdemeyer

• Description modified (diff)

Trivial rebase.

### comment:14 Changed 10 years ago by jdemeyer

• Milestone changed from sage-pending to sage-4.7.3

### comment:15 Changed 10 years ago by jdemeyer

• Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

### comment:16 Changed 10 years ago by jdemeyer

• Merged in set to sage-4.8.alpha1
• Milestone set to sage-4.8
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.