Karim BELABAS on Fri, 9 Aug 2002 13:54:14 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: rnfkummer-induced bug |
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/