Opened 10 years ago

Closed 9 years ago

# multivariate factorization over non-prime finite fields hangs

Reported by: Owned by: zimmerma tbd major sage-4.8 factorization sd35 malb, SimonKing sage-4.8.alpha6 Paul Zimmermann Bogdan Banu N/A

### 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.

### comment:1 Changed 10 years ago by zimmerma

• Keywords sd34 added

### comment:2 Changed 10 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 10 years ago by zimmerma

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

Paul

### 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.