Re: rnfkummer-induced bug

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

On Wed, 7 Aug 2002, Igor Schein wrote:
[ Igor's message was sent directly to me, I'm quoting the relevant bits ]

> On Wed, Aug 07, 2002 at 03:20:00AM +0200, Karim BELABAS wrote:
> > On Sun, 4 Aug 2002, Igor Schein wrote:
> > > ? setrand(1);rnfkummer(bnrinit(bnfinit(quadpoly(-8,y)),11,1),[5,2;0,1]);
> > >   ***   impossible inverse modulo: Mod(0, 11).
> >
> > It's gone now [typo].
> >
> > 1) I've axed further useless (and quite complicated) code in kummer.c, so
> > that rnfkummersimple (ell-th root of 1 already in K) re-uses the general
> > code (which had become much more efficient). The changes are non trivial
> > so I may have broken something in rnfkummersimple in the process.
>
> Actually, no, everything is very nice, and a solid performance improvement.
>
> I was hoping the new changes will allow me to tackle tough cases like
>
> bnf=bnfinit(quadpoly(181433,y));
> bnr=bnrinit(bnf,1,1);
> rnfkummer(bnr,0);
>
> After some time it gives me:
>
> #### Computing class group generators
> Time classgroup generators: 140
> split_ideal: increasing factor base [4]
[... ad lib]
>   ***   user interrupt after 15mn, 20,500 ms.
>
> Any idea what's going on there?

Yes. There was still one place in rnfkummer where algebraic numbers in
factored form could not be treated, so the factorization had to be
expanded / simplified. With exponents in the range of 5000 as here, it was
quite a lengthy process... and the result was completely unusable in any
case. In your example, gp was trying to recompute nf at precision 100000 or
so.

This had been left so because it involved modifying other routines (like
bnfisunit or bnfisprincipal). Since everything looked good so far, I've made
the necessary changes and your example is dealt with in about 1 minute.

I think now rnfkummer should be able to handle any field K for which
K(zeta_ell) can be computed [ and provided zeta_ell is in K or ell <= 5, but
this I will try to fix next ]

    Karim.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--
PARI/GP Home Page: http://www.parigp-home.de/