Opened 13 years ago

Closed 12 years ago

#9498 closed defect (fixed)

The function _factor_over_nonprime_finite_field is wrong in Sage, so remove it

Reported by: was Owned by: malb
Priority: major Milestone: sage-4.6.2
Component: commutative algebra Keywords:
Cc: Merged in: sage-4.6.2.alpha1
Authors: William Stein Reviewers: David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (3)

trac_9498-rebased_to_apply_after_5074.patch (2.9 KB) - added by was 13 years ago.
trac_9498.patch (3.3 KB) - added by was 13 years ago.
trac_9498.2.patch (3.3 KB) - added by jdemeyer 12 years ago.
Same patch, fixed commit message

Download all attachments as: .zip

Change History (8)

comment:1 Changed 13 years ago by was

Look into whether the comment malb posted on #5074 is really just an indication of a bug in this code, and not in Singular.

Changed 13 years ago by was

Attachment: trac_9498.patch added

comment:2 Changed 13 years ago by was

Status: newneeds_review

comment:3 Changed 12 years ago by davidloeffler

Authors: William Stein
Reviewers: David Loeffler
Status: needs_reviewpositive_review

Looks good to me. Since there seems to be no movement on #5074 -- I guess we're waiting for the Singular performance bug to be resolved -- let's at least deal with this ticket.

I tested sage/rings with trac_9498.patch applied and everything passed. Strictly speaking we should perhaps have a doctest, but since the patch adds no new code -- it just removes bad old code -- I don't think there's any need to insist on that.

comment:4 Changed 12 years ago by jdemeyer

Milestone: sage-4.6.1sage-4.6.2

Changed 12 years ago by jdemeyer

Attachment: trac_9498.2.patch added

Same patch, fixed commit message

comment:5 Changed 12 years ago by jdemeyer

Merged in: sage-4.6.2.alpha1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.