Ticket #11838 (closed defect: fixed)

Opened 21 months ago

Last modified 18 months ago

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 Work issues:
Report Upstream: N/A Reviewers: Bogdan Banu
Authors: Paul Zimmermann Merged in: sage-4.8.alpha6
Dependencies: Stopgaps:

Description

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

trac_11838.patch Download (1.2 KB) - added by zimmerma 18 months ago.

Change History

comment:1 Changed 21 months ago by zimmerma

  • Keywords sd34 added

comment:2 Changed 20 months 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 20 months ago by zimmerma

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

Paul

Changed 18 months ago by zimmerma

comment:4 Changed 18 months ago by zimmerma

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

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

comment:5 Changed 18 months ago by bbanu

  • Status changed from needs_review to positive_review

Looks good. Bogdan

comment:6 Changed 18 months ago by bbanu

  • Reviewers set to Bogdan Banu

comment:7 Changed 18 months ago by jdemeyer

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