#11890: Sage cannot factor polynomials over number fields with unfactorable
discriminant
-----------------------------+----------------------------------------------
Reporter: jdemeyer | Owner: davidloeffler
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.3
Component: number fields | Keywords: nffactor PARI nfinit pari_nf
Work_issues: | Upstream: N/A
Reviewer: | Author: Jeroen Demeyer
Merged: | Dependencies: #11891, #11130
-----------------------------+----------------------------------------------
Comment(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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11890#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
