LLL_FP64.h File Reference

A modified version of the LLL_FP module of NTL. More...

Namespaces
namespace	NTL
	These functions are in the NTL namespace.

Functions
long	NTL::LLL_FP64 (NTL::Mat< long > &B, const double delta=0.99, long r=0, long c=0, NTL::Vec< double > *sqlen=0)
	This function is similar to LLL_FP in NTL, but only the first r rows and first c columns of the matrix B are considered, and a basis is built for the lattice generated by these (partial) rows.
long	NTL::BKZ_FP64 (NTL::Mat< long > &BB, const double delta=0.99, long blocksize=10, long prune=0, long r=0, long c=0, NTL::Vec< double > *sqlen=0)
	This function is similar to BKZ_FP in NTL, with the same modifications as in LLL_FP64 above.

Detailed Description

A modified version of the LLL_FP module of NTL.

With the modified functions, the basis entries are in long, alias int64_t. We can also apply LLL or BKZ only to a submatrix (first r rows and c columns) of the matrix B that is passed in and returned. The returned basis will have c columns and at most max(r,c) rows (the rank of the basis matrix), so it may not occupy the entire space in B. With this flexibility, we can reserve a large block of memory for the matrix B and reuse this same block (the same object B) for thousands or millions of lattices that we want to analyze, even if the bases have different dimensions.

Another addition is the possibility to recover an array sqlen that gives the square Euclidean lengths of the basis vectors, in double. This array is maintained in the LLL_FP functions of NTL, but it is hidden in the implementation and not accessible from outside. In IntLattice, these lengths are maintained in a RealVec object. In this module, we assume that Real = double.

Each function returns the dimension of the computed basis (number of independent rows). This basis is always returned in the upper-left corner of the matrix B. This differs from the LLL_FP functions, which returns the zero vectors at the top.