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