Re: Bug rnfconductor

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

On 1 Oct 2002, I wrote:
> P.S: conductor() uses a highly inefficient algorithm, via
> orderofquotient() , computing many full bnr for different moduli, and many
> bnrisprincipal for each bnr, where the only question is whether all x = 1
> mod^* (f / v), (x, f) = 1 [ v a place in the support of the divisor f ]
> belong to the congruence subgroup or not [ and if so, incrementally for f /
> v^2, ... ].
>
> This can be checked trivially in (O_K / f)^* for the original f, since
> (O_K/f)^* / (O_K/(f/v))^* is cyclic with "obvious" generator.

This was wrong. Not always cyclic (only if v archimedean, or v^2 does not
divide f, or f has degree 1), but with obvious generators, yes.

> Using the general formalism for exact sequence of abelian groups from
> Cohen's (second) book is a real waste in this case.
>
> This code is copy-pasted in discrayrelall() and should be fixed here as
> well. I'll do it one of these days -- once I'm done checking late bug
> reports:-(

I've implemented these changes in both conductor() and discrayrelall(). This
affects [bnr|rnf]conductor(), bnrdisc(), and by extension most class field
routines [ it's a major change: the unified diff has ~ 1500 lines ].

The change makes it possible to use bnrconductor() [provided flag <= 0] and
bnrdisc() with a 'bnr' computed without generators: this was previously
required, although undocumented (I've also fixed the documentation).

  ? bnr = bnrinit(pol, f); bnrconductor(bnr)
  ***   please apply bnrinit(,,1) and not bnrinit(,).

The conductor() routine is now about 20 times faster for trivial examples,
and much more for complicated ones.

Unfortunately, there are still bottlenecks related to the bnr generators¹.
I shall try a second batch of patches in order to implement this second step,
but it's an even more complicated change.

Anything broken so far ? Igor ?

    Karim.

¹: or more exactly, to the use of bnr.gen: we could bypass them
completely (define them only abstractly), and have lightning fast

   bnrisprincipal(bnr2, bnr.gen[i]).

which is a basic operation in class field theoretic routines, without ever
needing to compute the generators [which is now very cheap, contrary to what
the doc implies]. But, more importantly, which have a completely inadequate
format for the above operation (and in fact for any operation besides perhaps
screen printing): they are naturally given in factored form, and fully
expanded in bnrinit() [ or idealstar() ]; using the expansion requires costly
transformations (basically recovering the factorization) _each time_ we
use a bnr for whatever purpose...

-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 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/