multivariate factorization over non-prime finite fields hangs

[zimmermann6]

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.

CC: @malb @simon-king-jena

Component: factorization

Keywords: sd35

Author: Paul Zimmermann

Reviewer: Bogdan Banu

Merged: sage-4.8.alpha6

Issue created by migration from https://trac.sagemath.org/ticket/11838

[zimmermann6]

Changed keywords from none to sd34

[a-andre]

comment:2

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)

[zimmermann6]

comment:3

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

Paul

[zimmermann6]

Author: Paul Zimmermann

[zimmermann6]

comment:4

Attachment: trac_11838.patch.gz

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

[zimmermann6]

Changed keywords from sd34 to sd35

[sagetrac-bbanu]

comment:5

Looks good. Bogdan

[sagetrac-bbanu]

Reviewer: Bogdan Banu

[jdemeyer]

Merged: sage-4.8.alpha6