#7097: bug in polynomial factorization over number fields
-----------------------+----------------------------------------------------
Reporter: cremona | Owner: tbd
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.2
Component: algebra | Keywords: polynomial factor root number field
Work_issues: | Author:
Reviewer: | Merged:
-----------------------+----------------------------------------------------
Changes (by cremona):
* status: new => needs_work
Comment:
I reported the bug to pari developers (it is bug #1006 there). Karim just
replied as follows:
{{{
* John Cremona [2009-10-02 18:42]:
> Factoring a non-monic integer polynomial of degree 9 over a number
> field of degree 24 yields an incomplete factorization.
[...]
> ? g = y^24 - 12*y^23 + 72*y^22 - 286*y^21 + 849*y^20 - 2022*y^19 +
> 4034*y^18 - 6894*y^17 + 10182*y^16 - 13048*y^15 + 14532*y^14 -
> 13974*y^13 + 11365*y^12 - 7578*y^11 + 4038*y^10 - 1766*y^9 + 762*y^8 -
> 408*y^7 + 236*y^6 - 126*y^5 + 69*y^4 - 38*y^3 + 18*y^2 - 6*y + 1
> %1 = y^24 - 12*y^23 + 72*y^22 - 286*y^21 + 849*y^20 - 2022*y^19 +
> 4034*y^18 - 6894*y^17 + 10182*y^16 - 13048*y^15 + 14532*y^14 -
> 13974*y^13 + 11365*y^12 - 7578*y^11 + 4038*y^10 - 1766*y^9 + 762*y^8 -
> 408*y^7 + 236*y^6 - 126*y^5 + 69*y^4 - 38*y^3 + 18*y^2 - 6*y + 1
> ? K = nfinit(g);
> ? f = 8*x^9 + 42*x^6 + 6*x^3 - 1
> %3 = 8*x^9 + 42*x^6 + 6*x^3 - 1
> ? nffactor(K,f)
>
> returns factors of degrees 1 and 8, but there should be 9 linear
> factors. In fact, K is the 4-division field of the elliptic curve
> [0,0,1,0,0] and f is the 4-division polynomial.
The logic used to handle non-monic polynomials in nffactor() was flawed,
leading to "increasing" leading coefficients that eventually became too
large compared to our a priori factor bound. Thus factors were missed.
Neither factornf(), nor nfroots() are affected.
Fixed in svn. The fix is non trivial and quite extensive, I won't be
able to backport it to pari-stable in a safe way. pari-stable user will
have to rely on factornf() to handle non-monic polynomials for a few
more months.
Cheers,
K.B.
}}}
Since it will be a while until this bugfix in pari percolates through to
Sage, I suggest that the code in Sage does a change of variables so that
the polynomial passed to pari's {{{nffactor()}}} is always monic.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7097#comment:5>
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
-~----------~----~----~----~------~----~------~--~---
