Karim BELABAS on Mon, 1 Jul 2002 23:42:46 +0200 (MEST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: bnfisintnorm() bug

On Mon, 1 Jul 2002, Igor Schein wrote:
> the following enters an infinite loop:
> bnfisintnorm(bnfinit(x^3+2),5);
> It was broken some time between 2.2.2 and 2.2.3 releases

A typo in idealmul(K, prime ideal, principal ideal). Fixed.

I had rewritten it in order to remove a silly hack: namely, the old
idealmul(K, pr, x) was setting

   M := [x * p | x * pi]   (assuming pr = (p,pi), multiplication in K)

then called idealhnf on M. The latter function first checks the rank of
the matrix; if it's < [K:Q], it "saturates" the matrix
(replaces it by the O_K-module generated by the columns), otherwise it
assumes the Z-module generated by the columns is actually an O_K module. For
a quadratic fields this didn't work, so this was special cased (replaced by
something even worse).

The current code sets M := [ m_(x*p) | m_(x*pi) ]
(m_z = multiplication table by z), and uses a standard HNF algorithm for M
without using (weird, undocumented) properties of the implementation. It's
also faster  [ which is unimportant since the routine is hardly ever used for
these arguments ]

Of course the idealprimedec structure should be modified so that the 'pi' and
'tau' components (uniformizer and anti-uniformizer) be replaced by their
multiplication table representation [ a large number of routines start by
replacing them by their multiplication table, as above, most importantly
nfelttval/idealval ].

Memory usage for factorbases would be multiplied by n = [K:Q], but a number
of other things would become n times faster.

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/