Re: bug in factronf()

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

[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
--
PARI/GP Home Page: http://pari.home.ml.org