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 )
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)
Change History (20)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Dependencies set to #11891
- Milestone changed from sage-4.7.2 to sage-4.7.3
Changed 8 years ago by
comment:3 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 8 years ago by
- Dependencies changed from #11891 to #11891, #11130
comment:5 follow-up: ↓ 6 Changed 8 years ago by
comment:6 in reply to: ↑ 5 Changed 8 years ago by
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: ↓ 8 Changed 8 years ago by
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
- 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
- Description modified (diff)
- Status changed from needs_work to needs_review
Changed 8 years ago by
Changed 8 years ago by
comment:10 Changed 8 years ago by
- 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
- 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
- Milestone changed from sage-4.7.3 to sage-pending
Changed 8 years ago by
comment:14 Changed 8 years ago by
- Milestone changed from sage-pending to sage-4.7.3
comment:16 Changed 8 years ago by
- 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
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:
I have to investigate this error. It might be a Pari bug or there are instances where we really need factornf.