Opened 9 years ago

Closed 9 years ago

#11838 closed defect (fixed)

multivariate factorization over non-prime finite fields hangs

Reported by: zimmerma Owned by: tbd
Priority: major Milestone: sage-4.8
Component: factorization Keywords: sd35
Cc: malb, SimonKing Merged in: sage-4.8.alpha6
Authors: Paul Zimmermann Reviewers: Bogdan Banu
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


In Sage 4.7.1:

sage: K = GF(4,'a')
sage: a = K.gens()[0]
sage: R.<x,y> = K[]
sage: p=x^8*y^3 + x^2*y^9 + a*x^9 + a*x*y^4
sage: q=y^11 + (a)*y^10 + (a + 1)*x*y^3
sage: p.factor(proof=False)
x * (x^7*y^3 + x*y^9 + (a)*x^8 + (a)*y^4)
sage: q.factor(proof=False)
y^3 * (y^8 + (a)*y^7 + (a + 1)*x)
sage: f = p*q
sage: f.factor(proof=False)

The last command seems to hang forever.

Attachments (1)

trac_11838.patch (1.2 KB) - added by zimmerma 9 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 9 years ago by zimmerma

  • Keywords sd34 added

comment:2 Changed 9 years ago by aapitzsch

I can confirm this in sage 4.7.1. But it don't happen in sage 4.7.2 anymore. I immediately get

x * y^3 * (y^8 + (a)*y^7 + (a + 1)*x) * (x^7*y^3 + x*y^9 + (a)*x^8 + (a)*y^4)

comment:3 Changed 9 years ago by zimmerma

I confirm it works with sage 4.7.2. I will add a non-regression test during the SageFlint? days.


Changed 9 years ago by zimmerma

comment:4 Changed 9 years ago by zimmerma

  • Authors set to Paul Zimmermann
  • Keywords sd35 added; sd34 removed
  • Status changed from new to needs_review

the attached patch adds a non-regression test. Please review it. Paul

comment:5 Changed 9 years ago by bbanu

  • Status changed from needs_review to positive_review

Looks good. Bogdan

comment:6 Changed 9 years ago by bbanu

  • Reviewers set to Bogdan Banu

comment:7 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.8.alpha6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.