Lattice Builder Manual
Software Package for Constructing Rank1 Lattices

For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest nonzero vector of the lattice using prereductions and a branchandbound (BB) algorithm [11] . More...
#include <Reducer.h>
Public Member Functions  
Reducer (IntLattice &lat)  
Constructor. More...  
Reducer (const Reducer &red)  
Copy constructor.  
~Reducer ()  
Destructor.  
Reducer &  operator= (const Reducer &red) 
Assignment operator.  
void  copy (const Reducer &red) 
Copies the reducer red into this object. More...  
void  transformStage3 (std::vector< long > &z, int &k) 
Method used in reductMinkowski to perform a transformation of stage 3 described in [1] . More...  
bool  calculCholeski (RVect &DC2, RMat &C0) 
Finds a Choleski decomposition of the basis. More...  
bool  tryZ (int j, int i, int Stage, bool &smaller, Base &WTemp) 
Tries to find shorter vectors in reductMinkowski .  
bool  tryZ0 (int j, bool &smaller) 
Tries to find a shorter vector in shortestVector .  
bool  shortestVector (NormType norm) 
Computes the shortest nonzero vector of this lattice with respect to norm norm using branchandbound and the algorithm described in [11] . More...  
bool  shortestVectorDieter (NormType norm) 
Similar to ShortestVector but uses the algorithm of Dieter [6], [10] .  
bool  redBB (int i, int d, int Stage, bool &smaller) 
Tries to shorten the vectors of the primal basis using branchandbound, in reductMinkowski .  
bool  redBB0 (NormType norm) 
Tries to shorten the smallest vector of the primal basis using branchandbound, in ShortestVector .  
void  preRedDieter (int d) 
Performs the reductions of the preceding two methods using cyclically all values of \(i\) (only for \(i > d\) in the latter case) and stops after either MaxPreRed successful transformations have been achieved or no further reduction is possible. More...  
bool  redDieter (NormType norm) 
Finds the shortest nonzero vector using norm norm . More...  
void  redLLL (double fact, long maxcpt, int dim) 
Performs a LLL (LenstraLenstraLovasz) basis reduction up to dimension dim with coefficient fact , which must be smaller than 1. More...  
bool  reductMinkowski (int d) 
Reduces the current basis to a Minkowski reduced basis with respect to the Euclidean norm, assuming that the first \(d\) vectors are already reduced and sorted. More...  
void  pairwiseRedPrimal (int i, int d) 
Performs pairwise reductions. More...  
void  pairwiseRedDual (int i) 
Performs pairwise reductions, trying to reduce every other vector of the {dual\/} basis by adding multiples of the \(i\)th vector. More...  
NScal  getMinLength () 
Returns the length of the shortest basis vector in the lattice.  
void  setBoundL2 (const NVect &V, int dim1, int dim2) 
Sets the lower bound on the square length of the shortest vector in dimension \(i\) to \(V[i]\), for \(i\) going from dim1 to dim2 .  
void  trace (char *mess) 
Debug function that print the primal and dual bases.  
Static Public Attributes  
static const long  SHORT_DIET = 1000 
Whenever the number of nodes in the branchandbound tree exceeds SHORT_DIET in the method ShortestVector , PreRedDieterSV is automatically set to true for the next call; otherwise it is set to false . More...  
static const long  SHORT_LLL = 1000 
Whenever the number of nodes in the branchandbound tree exceeds SHORT_LLL in the method ShortestVector , PreRedLLLSV is automatically set to true for the next call; otherwise it is set to false . More...  
static const long  MINK_LLL = 500000 
Whenever the number of nodes in the branchandbound tree exceeds MINK_LLL in the method reductMinkowski , PreRedLLLRM is automatically set to true for the next call; otherwise it is set to false .  
static const long  MAX_PRE_RED = 1000000 
Maximum number of transformations in the method PreRedDieter . More...  
static long  maxNodesBB 
The maximum number of nodes % that we are ready to accept in the branchandbound tree when calling ShortestVector or reductMinkowski . More...  
static bool  PreRedDieterSV 
These boolean variables indicate which type of prereduction is to be performed for ShortestVector (SV) and for reductMinkowski (RM). More...  
static bool  PreRedLLLSV 
static bool  PreRedLLLRM 
For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest nonzero vector of the lattice using prereductions and a branchandbound (BB) algorithm [11] .
It also implements the method of Lenstra, Lenstra and Lovasz (LLL) [15] as well as the method of Dieter [6] to reduce a lattice basis. The reduction algorithms in this class use both the primal and the dual lattices, so both lattices must be defined.
LatCommon::Reducer::Reducer  (  IntLattice &  lat  ) 
Constructor.
Initializes the reducer to work on lattice lat
.
bool LatCommon::Reducer::calculCholeski  (  RVect &  DC2, 
RMat &  C0  
) 
Finds a Choleski decomposition of the basis.
Returns in C0
the elements of the upper triangular matrix of the Choleski decomposition that are above the diagonal. Returns in DC2
the squared elements of the diagonal.
void LatCommon::Reducer::copy  (  const Reducer &  red  ) 
Copies the reducer red
into this object.
void LatCommon::Reducer::pairwiseRedDual  (  int  i  ) 
Performs pairwise reductions, trying to reduce every other vector of the {dual\/} basis by adding multiples of the \(i\)th vector.
That may change the \(i\)th vector in the primal basis. Each such dual reduction is actually performed only if that does not increase the length of vector \(i\) in the primal basis. Always uses the Euclidean norm.
void LatCommon::Reducer::pairwiseRedPrimal  (  int  i, 
int  d  
) 
Performs pairwise reductions.
This method tries to reduce each basis vector with index larger than \(d\) and distinct from \(i\) by adding to it a multiple of the \(i\)th vector. Always uses the Euclidean norm.
void LatCommon::Reducer::preRedDieter  (  int  d  ) 
Performs the reductions of the preceding two methods using cyclically all values of \(i\) (only for \(i > d\) in the latter case) and stops after either MaxPreRed
successful transformations have been achieved or no further reduction is possible.
Always use the Euclidean norm.
bool LatCommon::Reducer::redDieter  (  NormType  norm  ) 
void LatCommon::Reducer::redLLL  (  double  fact, 
long  maxcpt,  
int  dim  
) 
Performs a LLL (LenstraLenstraLovasz) basis reduction up to dimension dim
with coefficient fact
, which must be smaller than 1.
If fact
is closer to 1, the basis will be (typically) ``more reduced'', but that will require more work. The reduction algorithm is applied until maxcpt
successful transformations have been done. Always uses the Euclidean norm.
bool LatCommon::Reducer::reductMinkowski  (  int  d  ) 
Reduces the current basis to a Minkowski reduced basis with respect to the Euclidean norm, assuming that the first \(d\) vectors are already reduced and sorted.
If MaxNodesBB
is exceeded during {one} of the branchandbound step, the method aborts and returns false
. Otherwise it returns true
, the basis is reduced and sorted by vector lengths (the shortest vector is V
[1] and the longest is V
[Dim]). % This method does not care about numerical imprecision due to the % (64bit) floatingpoint representation. % In this sense, the results are not 100% reliable.
bool LatCommon::Reducer::shortestVector  (  NormType  norm  ) 
Computes the shortest nonzero vector of this lattice with respect to norm norm
using branchandbound and the algorithm described in [11] .
The Norm
member of this object will be changed to norm
. If MaxNodesBB
is exceeded during {one} of the branchandbounds, the method aborts and returns false
. Otherwise, it returns true
. Uses the prereduction algorithms of Dieter and of LenstraLenstraLovasz.
void LatCommon::Reducer::transformStage3  (  std::vector< long > &  z, 
int &  k  
) 
Method used in reductMinkowski
to perform a transformation of stage 3 described in [1] .
Also used in ShortestVector
. Assumes that \(\sum_{i=1}^t z_i V_i\) is a short vector that will enter the basis. Tries to reduce some vectors by looking for indices \(i < j\) such that \(z_j > 1\) and \(q=\lfloor z_i/z_j\rfloor \not=0\), and adding \(q V_i\) to \(V_j\) when this happens. Returns in \(k\) the last index \(j\) such that \(z_j=1\).

static 
Maximum number of transformations in the method PreRedDieter
.
After MAX_PRE_RED
successful transformations have been performed, the prereduction is stopped.

static 
The maximum number of nodes % that we are ready to accept in the branchandbound tree when calling ShortestVector
or reductMinkowski
.
When this number is exceeded, the method aborts and returns false
.

static 
These boolean variables indicate which type of prereduction is to be performed for ShortestVector
(SV) and for reductMinkowski
(RM).
Dieter
means the pairwise prereduction as in the method PreRedDieter
. LLL
means the LLL reduction of Lenstra, Lenstra, and Lov\'asz. The variable PreRedDieterSV
is originally set to true
and the two others are originally set to false
. These variables are reset automatically depending on the thresholds MinkLLL, ShortDiet, ShortLLL
as explained above.

static 
Whenever the number of nodes in the branchandbound tree exceeds SHORT_DIET
in the method ShortestVector
, PreRedDieterSV
is automatically set to true
for the next call; otherwise it is set to false
.
The default value is 1000.

static 
Whenever the number of nodes in the branchandbound tree exceeds SHORT_LLL
in the method ShortestVector
, PreRedLLLSV
is automatically set to true
for the next call; otherwise it is set to false
.
% The default value is 1000.