Re: yet another nfdisc() bug

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

> this time I supply a nice monic irreducible polynomial to nfdisc():
> 
> ? nfdisc(x^18+16)
>   ***   impossible inverse modulo: Mod(0, 2).
> 
> Again, one of the newly-introduced bugs ( 2.0.11 is clean ).

Conceptual bug: the code was originally written so that a polynomial would
have integer coefficients for better efficiency, and (in dire
circonstances) it had not, which made the original code inefficient
in those rare cases.

My improvement used this hypothesis, hence was not correct. The following
patch corrects this problem by computing things in the right order so that
everybody indeed has integer coefficients.

Karim.

P.S: Note: nfdisc(x^18+16) took 5.4 s in 2.0.11, down to 4.0s after the
patch, hence the "inefficiency" was not only theoretical.

*** src/basemath/base2.c.orig   Fri Nov  6 16:08:03 1998
--- src/basemath/base2.c        Tue Dec  1 16:45:23 1998
***************
*** 1184,1200 ****
  static GEN
  eltppm(GEN f,GEN pd,GEN theta,GEN k)
  {
!   GEN pdd,phi,psi,q;
    long av=avma,tetpil;
  
!   pdd=sqri(pd);
    phi=pd; psi=gmul(pd,theta); q=k;
  
    for(;;)
    {
!     if (mod2(q)) phi = Fp_res(gdiv(gmul(phi,psi),pd), f, pdd);
      q=shifti(q,-1); if (!signe(q)) break;
!     psi = Fp_res(gdiv(gsqr(psi),pd), f, pdd);
    }
    tetpil=avma; return gerepile(av,tetpil,gdiv(phi,pd));
  }
--- 1184,1200 ----
  static GEN
  eltppm(GEN f,GEN pd,GEN theta,GEN k)
  {
!   GEN p3d,phi,psi,q;
    long av=avma,tetpil;
  
!   p3d=mulii(sqri(pd), pd);
    phi=pd; psi=gmul(pd,theta); q=k;
  
    for(;;)
    {
!     if (mod2(q)) phi = gdiv(Fp_res(gmul(phi,psi), f, p3d), pd);
      q=shifti(q,-1); if (!signe(q)) break;
!     psi = gdiv(Fp_res(gsqr(psi), f, p3d), pd);
    }
    tetpil=avma; return gerepile(av,tetpil,gdiv(phi,pd));
  }

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