Karim BELABAS on Tue, 8 Dec 1998 17:51:02 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

 Re: bug in factronf()

```[Igor:]
> this is a what I call "bad input" bug.
> ? factornf(x^3+2,y^2-1)
>   ***   non-invertible polynomial in polinvmod. \\ correct error message
> ? factornf(x^3+1,y^2-1)
>   ***   the PARI stack overflows !!!
>
>   ***   Warning: doubling stack size; new stack = 8000000.
>
> So factornf() gets confused when both polynomials are reducible and
> keeps growing the stack.  This bug was introduced somewhere between
> 2.0.11.beta and 2.0.12.alpha.

It's due to the fact that the output of factor() is now sorted: we reduce to
a factorization problem over Z, and if the "modulus" polynomial is not
irreducible, the output is not really usable. When converting back to the
original problem, a different "bad" factor is considered first. So, instead
of trying to invert a non-invertible polmod, we find 1 as an irreducible
factor, then try to compute the valuation at 1...

The patch below shoudl correct it (apply my preceding patch [msg 329] before
this one).

Karim.

*** src/basemath/polarit2.c.orig	Tue Dec  8 17:20:47 1998
--- src/basemath/polarit2.c	Tue Dec  8 17:37:32 1998
***************
*** 2256,2287 ****
GEN
polfnf(GEN a, GEN t)
{
!   GEN y,p1,p2,u,g,fa,n,unt,f,b,pro;
!   long av=avma,tetpil,lx,v,i,e,k,vt;

if (typ(a)!=t_POL || typ(t)!=t_POL) err(typeer,"polfnf");
if (gcmp0(a)) return gcopy(a);
vt=varn(t); v=varn(a);
if (vt<v)
err(talker,"polynomial variable must be of higher priority than number field variable\nin factornf");
!   u = gdiv(a,ggcd(a,derivpol(a)));
unt = gmodulsg(1,t); u = gmul(unt,u);
!   g=lift(u); k = -2;
!   do
{
!     k++; n = gsub(polx[MAXVARN], gmulsg(k,polx[vt]));
n = subres(t, poleval(g,n));
}
-   while (lgef(modulargcd(n,derivpol(n))) > 3);
fa=factor(n); fa=(GEN)fa[1]; lx=lg(fa);
y=cgetg(3,t_MAT);
p1=cgetg(lx,t_COL); y[1]=(long)p1;
p2=cgetg(lx,t_COL); y[2]=(long)p2;
for (i=1; i<lx; i++)
{
!     f = poleval((GEN)fa[i], gadd(polx[v],gmulsg(k,gmodulcp(polx[vt],t))));
!     pro = ggcd(u, gmul(unt,f));
p1[i] = (typ(pro)==t_POL)? ldiv(pro,leading_term(pro)): (long)pro;
e=0; while (poldivis(a,(GEN)p1[i], &b)) { a = b; e++; }
p2[i] = lstoi(e);
}
--- 2256,2290 ----
GEN
polfnf(GEN a, GEN t)
{
!   GEN x0, y,p1,p2,u,g,fa,n,unt;
!   long av=avma,tetpil,lx,v,i,k,vt;

if (typ(a)!=t_POL || typ(t)!=t_POL) err(typeer,"polfnf");
if (gcmp0(a)) return gcopy(a);
vt=varn(t); v=varn(a);
if (vt<v)
err(talker,"polynomial variable must be of higher priority than number field variable\nin factornf");
!   u = gdiv(a, ggcd(a,derivpol(a)));
unt = gmodulsg(1,t); u = gmul(unt,u);
!   g = lift(u);
!   for (k=-1; ; k++)
{
!     n = gsub(polx[MAXVARN], gmulsg(k,polx[vt]));
n = subres(t, poleval(g,n));
+     if (lgef(modulargcd(n,derivpol(n))) == 3) break;
}
fa=factor(n); fa=(GEN)fa[1]; lx=lg(fa);
y=cgetg(3,t_MAT);
p1=cgetg(lx,t_COL); y[1]=(long)p1;
p2=cgetg(lx,t_COL); y[2]=(long)p2;
+   x0 = gadd(polx[v],gmulsg(k,gmodulcp(polx[vt],t)));
for (i=1; i<lx; i++)
{
!     GEN b, pro = ggcd(u, gmul(unt, poleval((GEN)fa[i], x0)));
!     long e;
!
p1[i] = (typ(pro)==t_POL)? ldiv(pro,leading_term(pro)): (long)pro;
+     if (gcmp1((GEN)p1[i])) err(talker,"reducible modulus in factornf");
e=0; while (poldivis(a,(GEN)p1[i], &b)) { a = b; e++; }
p2[i] = lstoi(e);
}
--
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--