Opened 9 years ago

Closed 9 years ago

#12928 closed defect (duplicate)

critical bug in multivariate polynomial factorization over GF(2)

Reported by: zimmerma Owned by: tbd
Priority: critical Milestone: sage-duplicate/invalid/wontfix
Component: factorization Keywords:
Cc: malb Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

consider the following (both with Sage 4.8 and Sage 5.0.beta13 without proof=False):

sage: R.<x,y>=GF(2)[]
sage: factor(x^6 + y^6 + x^5 + x^3 + x + 1,proof=False)
x^6 + y^6 + x^5 + x^3 + x + 1
sage: (x^4+y^2*x^2+x^2+y^2*x+y^4+y^2+1)*(x^2+x+y^2+1)     
x^6 + y^6 + x^5 + x^3 + x + 1

This seems to be a bug in Singular factorization. I set the priority to "critical" since this is really a very basic routine.

Paul

Change History (10)

comment:1 Changed 9 years ago by zimmerma

  • Cc malb added

comment:2 Changed 9 years ago by zimmerma

here is another example:

sage: R.<x,t> = GF(2)[]
sage: f=x^6 + (t^5 + t^2)*x + t^5 + t^4 + t^3 + 1
sage: factor(f,proof=False)                      
x^6 + x*t^5 + t^5 + t^4 + x*t^2 + t^3 + 1
sage: f % (x+t+1)
0

Note that the factorization algorithm seems not to be deterministic, thus some times the factorization is correct.

Paul

comment:3 Changed 9 years ago by zimmerma

Note that for the example given in the description, the "bug" seems to be deterministic.

Paul

comment:4 Changed 9 years ago by malb

Hi, can you guys report this upstream? I am travelling this week.

comment:5 Changed 9 years ago by zimmerma

  • Report Upstream changed from N/A to Reported upstream. Little or no feedback.

comment:6 Changed 9 years ago by zimmerma

  • Report Upstream changed from Reported upstream. Little or no feedback. to Fixed upstream, in a later stable release.

the bug is fixed upstream. I have asked in which release the patch will be.

Paul

comment:7 Changed 9 years ago by zimmerma

upstream says it is fixed in 3-1-4-4.

Paul

comment:8 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.3 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

Fixed by #13237.

comment:9 Changed 9 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:10 Changed 9 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.