Factoring over GF(p) is broken

[dreyer]

Bug report by William Stein:

Factorization of polynomials over GF(p) is broken in all versions

of Singular in the last four years, including the just-released 3-1-0, and on all platforms. E.g., below I factor a polynomial over GF(3) twice, and get different answers.

wstein@sage:~/tmp/Singular/3-1-0$ x86_64-Linux/Singular
                     SINGULAR                             /
 A Computer Algebra System for Polynomial Computations   /   version 3-1-0
                                                       0<
     by: G.-M. Greuel, G. Pfister, H. Schoenemann        \   Mar 2009
FB Mathematik der Universitaet, D-67653 Kaiserslautern    \
> > LIB "general.lib"
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/general.lib (1.62,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/matrix.lib (1.48,2009/04/10)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/nctools.lib (1.52,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/random.lib (1.20,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/ring.lib (1.34,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/primdec.lib (1.147,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/absfact.lib (1.7,2008/07/16)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/triang.lib (1.14,2009/04/14)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/elim.lib (1.32,2009/04/16)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/poly.lib (1.53,2009/04/15)
// ** loaded /home/wstein/tmp/Singular/3-1-0/LIB/inout.lib (1.34,2009/04/15)
. ;
> > ring R=3,(x,y,z),lp;
> > def f=-y8z4+y8z3+y8z-y8+y7z6-y7z4-y7z3+y7z-y6z7+y6z5+y6z4-y6z2+y5z10-y5z9-y5z4+y5z3+y5z-y5-y4z12+y4z10+y4z6-y4z4-y4z3+y4z2+y3z13-y3z11-y3z7+y3z5-y3z4+y3z3+y3z2+y3z-y2z13+y2z12+y2z7-y2z5-y2z3-y2z2-y2z+y2+yz15-yz13-yz9-yz7+yz5-yz4+yz3+yz2+y-z16+z14+z10+z6+z4;
> >
. factorH(f);
[1]:
   _[1]=-1
   _[2]=y4z2+y4z+y4+y3z4-y3z3-y3z2+y3+y2z6-y2z5-y2z4-y2z3-y2z+yz7+yz5-yz4+yz3+yz2+y+z8+z6+z4
   _[3]=y4z2+y4z+y4+y3z4-y3z3-y3z2-y3z-y3+y2z6-y2z5-y2z4+y2z+y2+yz7+yz5+yz4+yz3-yz2-y+z8+z6+z4-1
[2]:
   1,1,1
> > factorH(f);
[1]:
   _[1]=-1
   _[2]=y8z4-y8z3-y8z+y8-y7z6+y7z4+y7z3-y7z+y6z7-y6z5-y6z4+y6z2-y5z10+y5z9+y5z4-y5z3-y5z+y5+y4z12-y4z10-y4z6+y4z4+y4z3-y4z2-y3z13+y3z11+y3z7-y3z5+y3z4-y3z3-y3z2-y3z+y2z13-y2z12-y2z7+y2z5+y2z3+y2z2+y2z-y2-yz15+yz13+yz9+yz7-yz5+yz4-yz3-yz2-y+z16-z14-z10-z6-z4
[2]:

[seelisch]

here's the input from old ticket #2: ring r = (0,a),(x,y),dp; minpoly = a^{2 +1; poly f = (x-a)*(y-a); sqrfree(f); factorize(f);}

---

ring r=(2,a),(U(1..3)),dp;minpoly=a2+a+1; matrix m[3][3]=U(1),U(2),U(3),U(2),U(3),U(1),U(3),U(1),U(2); poly d=det(m); factorize(d);

poly f=(U(1)+a*U(2)+a2*U(3))*(U(1)+a2*U(2)+a*U(3))*(U(1)+U(2)+U(3));

---

ring r = (3,a),(x,y),dp; minpoly = a^{2 + 2*a + 2; poly f = (x-a)*(y-a); factorize(f);}

[seelisch]

here's the input from old ticket #124: Ich forwarde drei mails von William Stein. Die erste befasst sich mit einem bug. Gruss, Wolfram Decker

---

Subject: bug: poly factoring in small characteristic From: "William Stein" <wstein@…> Date: Wed, March 11, 2009 6:06 pm To: decker@…

---

This uses Singular:

sage: R.<x,y> = PolynomialRing?(GF(3),2) sage: h = - (-x2 - x*y + y2 - 1)2 * (x2*y2 + y4 + x2*y + x*y2 + y3 - x2 + x*y + y2 - 1) * (-x4 - x3*y - x*y3 + y4 - x3 + x2*y + x*y2 - x2 - x*y - y2 + x + 1) sage: h.factor(proof=False) (-1) * (-x2 - x*y + y2 - 1) * (x8*y2 - x7*y3 + x6*y4 - x5*y5 + x3*y7 + x2*y8 + x*y9 + y10 + x8*y + x7*y2 - x3*y6 - x2*y7 + y9 - x8 + x3*y5 + x*y7 - y8 - x7 + x4*y3 + x3*y4

• x2*y5 + y7 - x4*y2 + x3*y3 + x2*y4 + x*y5 - y6 - x5 -

x4*y - y5 + x4 - x3*y + x2*y2 + x3 + x*y2 - y3 + x2 - x*y + x + 1) sage: h.factor(proof=False) (-1) * (-x2 - x*y + y2 - 1)2 * (x2*y2 + y4 + x2*y + x*y2 + y3

• x2 + x*y + y2 - 1) * (-x4 - x3*y - x*y3 + y4 - x3 + x2*y +

x*y2 - x2 - x*y - y2 + x + 1)

sage: z = singular(h) sage: z.factorize()

[1]:

_[1]=-1 _[2]=x2*y2+y4+x2*y+x*y2+y3-x2+x*y+y2-1 _[3]=x6-x5*y+x*y5+y6+x5+x*y4-x4+x2*y2+x*y3+y4+x2*y-y2-x-1 _[4]=-x2-x*y+y2-1

[2]:

1,1,1,1

sage: z.factorize()

[1]:

_[1]=-1 _[2]=x2*y2+y4+x2*y+x*y2+y3-x2+x*y+y2-1 _[3]=-x4-x3*y-x*y3+y4-x3+x2*y+x*y2-x2-x*y-y2+x+1 _[4]=-x2-x*y+y2-1

[2]:

1,1,1,2

-- William Stein Associate Professor of Mathematics University of Washington ​http://wstein.org

[seelisch]

here's the input from old ticket #178: reported by Sascha Kurz, 27 Oct 2009:

Singular : signal 8 (v: 3042/2008110900): Segment fault/Bus error occurred at 7fff2d0ac8e0 because of 10256 (r:1256645513) please inform the authors trying to restart..

Here's the code:

option(redSB); ring R=0,(x(1..16),y(1..16)),lp; poly f1 = x(1); poly f2 = y(1); poly f3 = x(2) -1; poly f4 = y(2); poly f5 = (x(1)-x(4))^{2 + (y(1)-y(4))}2 - 1; poly f6 = (x(2)-x(4))^{2 + (y(2)-y(4))}2 - 1; poly f7 = (x(2)-x(5))^{2 + (y(2)-y(5))}2 - 1; poly f8 = (x(4)-x(5))^{2 + (y(4)-y(5))}2 - 1; poly f9 = (x(2)-x(3))^{2 + (y(2)-y(3))}2 - 1; poly f10 = (x(5)-x(3))^{2 + (y(5)-y(3))}2 - 1; poly f11 = (x(1)-x(6))^{2 + (y(1)-y(6))}2 - 1; poly f12 = (x(6)-x(7))^{2 + (y(6)-y(7))}2 - 1; poly f13 = (x(7)-x(3))^{2 + (y(7)-y(3))}2 - 1; poly f14 = (x(12)-x(3))^{2 + (y(12)-y(3))}2 - 1; poly f15 = (x(7)-x(12))^{2 + (y(7)-y(12))}2 - 1; poly f16 = (x(7)-x(11))^{2 + (y(7)-y(11))}2 - 1; poly f17 = (x(12)-x(11))^{2 + (y(12)-y(11))}2 - 1; poly f18 = (x(11)-x(13))^{2 + (y(11)-y(13))}2 - 1; poly f19 = (x(12)-x(13))^{2 + (y(12)-y(13))}2 - 1; poly f20 = (x(10)-x(6))^{2 + (y(10)-y(6))}2 - 1; poly f21 = (x(10)-x(11))^{2 + (y(10)-y(11))}2 - 1; poly f22 = (x(1)-x(8))^{2 + (y(1)-y(8))}2 - 1; poly f23 = (x(6)-x(8))^{2 + (y(6)-y(8))}2 - 1; poly f24 = (x(10)-x(8))^{2 + (y(10)-y(8))}2 - 1; poly f25 = (x(9)-x(8))^{2 + (y(9)-y(8))}2 - 1; poly f26 = (x(10)-x(9))^{2 + (y(10)-y(9))}2 - 1; poly f27 = (x(14)-x(9))^{2 + (y(14)-y(9))}2 - 1; poly f28 = (x(14)-x(13))^{2 + (y(14)-y(13))}2 - 1; poly f29 = (x(15)-x(9))^{2 + (y(15)-y(9))}2 - 1; poly f30 = (x(15)-x(14))^{2 + (y(15)-y(14))}2 - 1; poly f31 = (x(15)-x(16))^{2 + (y(15)-y(16))}2 - 1; poly f32 = (x(16)-x(14))^{2 + (y(16)-y(14))}2 - 1; poly f33 = (x(16)-x(13))^{2 + (y(16)-y(13))}2 - 1; poly f34 = (x(1)-x(9))^{2 + (y(1)-y(9))}2 - 4; poly f35 = (x(9)-x(13))^{2 + (y(9)-y(13))}2 - 4; poly f36 = (x(13)-x(3))^{2 + (y(13)-y(3))}2 - 4; poly f37 = (x(1)-x(10))^{2 + (y(1)-y(10))}2 - 3; poly f38 = (x(9)-x(6))^{2 + (y(9)-y(6))}2 - 3; poly f39 = (x(16)-x(9))^{2 + (y(16)-y(9))}2 - 3; poly f40 = (x(15)-x(13))^{2 + (y(15)-y(13))}2 - 3; poly f41 = (x(11)-x(3))^{2 + (y(11)-y(3))}2 - 3; poly f42 = (x(7)-x(13))^{2 + (y(7)-y(13))}2 - 3; poly f43 = 2*x(4)-1; poly f44 = 4*y(4)-3; poly f45 = 2*x(5)-3; poly f46 = y(4)-y(5); poly f47 = x(3)-2; poly f48 = y(3); poly f49 = x(13)-9; poly f50 = (x(7)-x(6))*(y(11)-y(10))-(x(11)-x(10))*(y(7)-y(6)); poly f51 = (x(10)-x(6))*(y(11)-y(7))-(x(11)-x(7))*(y(10)-y(6)); ideal I=f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11,f12,f13,f14,f15,f16,f17,f18,f19,f20,f21,f22,f23,f24,f25,f26,f27,f28,f29,f30,f31,f32,f33,f34,f35,f36,f37,f38,f39,f40,f41,f42,f43,f45,f46,f47,f48; list L = facstd(I); size(L); L;

[hannes]

seems that the new factorize code fixes the problems for char p (and extensions), but extensions in char 0 are still (sometimes) broken