#9498: The function _factor_over_nonprime_finite_field is wrong in Sage, so
remove
it
-----------------------------------+----------------------------------------
Reporter: was | Owner: malb
Type: defect | Status: new
Priority: major | Milestone: sage-4.5.1
Component: commutative algebra | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
I wrote the function _factor_over_nonprime_finite_field in
multi_polynomial.pyx in hopes that Singular's multivariate poly
factorization worked over GF(p). But it doesn't, so that function is
pointless. Moreover, as John Cremona pointed out in email on the
sagedays23 list recently, the algorithm there is wrong!:
{{{
If f is irreducible over R but not over S then your
gcd will be f again which does not help you factor over S.
Basically what one needs is that the conjugates of f (whose product is
the norm) are coprime.
?
}}}
Here's an example to illustrate that it is wrong:
{{{
flat:polynomial wstein$ sage
----------------------------------------------------------------------
| Sage Version 4.4.4, Release Date: 2010-06-23 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: R.<x> = GF(3)[]
sage: x^2+1
x^2 + 1
sage: (x^2+1).factor()
x^2 + 1
sage: f = x^2+1
sage: f
x^2 + 1
sage: g = f.change_ring(GF(9,'a'))
sage: g
x^2 + 1
sage: g.factor()
(x + a + 1) * (x + 2*a + 2)
sage: type(g)
<type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
sage: R.<x,y> = GF(3)[]
sage: f = x^2+1
sage: g = f.change_ring(GF(9,'a'))
sage: g
x^2 + 1
sage: g.factor()
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call
last)
/Users/wstein/sage/build/sage-4.4.4/devel/sage-
main/sage/rings/polynomial/<ipython console> in <module>()
/Users/wstein/sage/build/sage-4.4.4/local/lib/python2.6/site-
packages/sage/rings/polynomial/multi_polynomial_libsingular.so in
sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.factor
(sage/rings/polynomial/multi_polynomial_libsingular.cpp:22745)()
3586 raise NotImplementedError, "Factorization of
multivariate polynomials over prime fields with characteristic > 2^29 is
not implemented."
3587 if proof:
-> 3588 raise NotImplementedError, "proof = True
factorization not implemented. Call factor with proof=False."
3589 if not self._parent._base.is_prime_field():
3590 return self._factor_over_nonprime_finite_field()
NotImplementedError: proof = True factorization not implemented. Call
factor with proof=False.
sage: g._factor_over_nonprime_finite_field()
x^2 + 1
sage: g.factor(proof=False)
x^2 + 1
}}}
The point is that g should factor as a product of two linear factors.
So, let's just delete this function, and anything that calls it, and use
Singular's builtin factorization code in the non-prime case.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9498>
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.
