Gerhard Niklasch on Wed, 9 Sep 1998 19:19:19 +0200 (MET DST)


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

Re: Number field with prescribed integral basis


In response to
> Message-ID:
>  <Pine.LNX.3.95.980909162454.28345B-100000@wisk10.wi.leidenuniv.nl>
> Date: Wed, 9 Sep 1998 16:42:29 +0200 (MET DST)
> From: "N.Bruin" <nbruin@zeus.wi.leidenuniv.nl>
> 
> I would like to have a representation of a number field K (a bnf,
> say) with a prescribed integral basis. I want the basis to be LLL reduced,
> to be precise.

I'm not sure this is possible with the current implementation  (because
several functions may rely on nf[7], aka nf.zk, and nf[8] -- which
express the integral basis of Z_K in terms of a power basis of some
sub-order, and vice versa -- to be in HNF, or at least triangular,
and LLL-reducing the integral basis would in general destroy both
properties).

Your second best bet may be to choose the defining polynomial carefully.
Some experimentation may be needed to find out whether polred() or
polredabs() gives better results.  (The latter is `almost canonical',
but may fail to return a power basis generator even when one exists.
It does guarantee, however, that the generating element will be as
short as possible, for one precise notion of shortness.)

Alternatively, or in addition to it:  construct a suitable quadratic
form from the various matrices in the nf structure  (you could use
nf.t2 directly as the Gram matrix),  LLL-reduce nf.zk as a lattice
basis with respect to that  (i.e. feed the Gram matrix to qflllgram()
with suitable flags),  disregarding the multiplicative structure for
the moment, and simply enumerate short vectors in that lattice.  When
necessary, use the transformation matrix returned by LLL to convert
them back to nf coordinates before feeding them to any nf...() functions.

Beware numerical instability  (nf.t2 has non-integer entries except
in degenerate cases).

Hope this helps,
Gerhard