Opened 8 years ago

Closed 8 years ago

#11890 closed enhancement (fixed)

Sage cannot factor polynomials over number fields with unfactorable discriminant

Reported by: jdemeyer Owned by: davidloeffler
Priority: major Milestone: sage-4.8
Component: number fields Keywords: nffactor PARI nfinit pari_nf
Cc: Merged in: sage-4.8.alpha1
Authors: Jeroen Demeyer Reviewers: Luis Felipe Tabera Alonso
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11891, #11130 Stopgaps:

Description (last modified by jdemeyer)

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: K = QuadraticField(p*q)
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().

See also #10910.

Apply 11890_rebased.patch, 11890_try_nffactor.patch and 11890_reviewer.patch.

Attachments (4)

11890.patch (13.6 KB) - added by jdemeyer 8 years ago.
11890_try_nffactor.patch (5.2 KB) - added by jdemeyer 8 years ago.
11890_reviewer.patch (1.9 KB) - added by lftabera 8 years ago.
11890_rebased.patch (13.6 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 8 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

Changed 8 years ago by jdemeyer

comment:3 Changed 8 years ago by jdemeyer

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

comment:4 Changed 8 years ago by jdemeyer

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

comment:5 follow-up: Changed 8 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 8 years ago by jdemeyer

Replying to lftabera:

  • 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: Changed 8 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 8 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to lftabera:

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 8 years ago by jdemeyer

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

Changed 8 years ago by jdemeyer

Changed 8 years ago by lftabera

comment:10 Changed 8 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 8 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 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.3 to sage-pending

Changed 8 years ago by jdemeyer

comment:13 Changed 8 years ago by jdemeyer

  • Description modified (diff)

Trivial rebase.

comment:14 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-4.7.3

comment:15 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:16 Changed 8 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.