This ReducerBB class provides facilities to reduce the basis of a lattice (an IntLattice object) in various ways (pairwise, LLL, BKZ, Minkowski [4], [9], [10]), and to find a shortest nonzero vector in the lattice using a BB algorithm [rFIN85a]. More...

#include <latticetester/ReducerBB.h>

Public Member Functions
	ReducerBB (IntLattice< Int, Real > &lat)
	Constructor that initializes the reducer to work on the lattice `lat`.

	ReducerBB (int64_t maxDim)
	Constructor of a `ReducerBB` than can handle up to `maxDim` dimensions.

	ReducerBB (const ReducerBB< Int, Real > &red)
	Copy constructor.

	~ReducerBB ()
	Destructor.

ReducerBB< Int, Real > &	operator= (const ReducerBB< Int, Real > &red)
	Assignment operator that makes a deep copy of `red` into the current object, using `copy`.

void	init (int64_t maxDim)
	Initializes all matrices used in the following.

void	copy (const ReducerBB< Int, Real > &red)
	Copies `red` into the current object.

bool	shortestVector ()
	Computes a shortest non-zero vector for the `IntLattice` stored in this `ReducerBB` object, with respect to the norm in this `IntLattice`, using the BB algorithm described in [6] and [7].

bool	shortestVector (IntLattice< Int, Real > &lat)
	In this version, the lattice is passed as a parameter.

bool	reductMinkowski (int64_t d=0)
	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.

bool	reductMinkowski (IntLattice< Int, Real > &lat, int64_t d=0)
	In this version, the lattice is passed as a parameter.

void	redDieter (int64_t dim, bool taboo[]=NULL)
	This method performs pairwise reduction sequentially on all vectors of the basis whose indices are greater of equal to `dim >=0`, as proposed in [4].

void	redDieterRandomized (int64_t dim, int64_t seed)
	Same as `redDieter(dim)` but the choice of vectors on which to perform pairwise reduction is randomized, using a simple RNG from the standard C library, with the given integer seed.

void	redLLLOld (double delta=0.999999, std::int64_t maxcpt=1000000000, int64_t dim=0)
	This is an old implementation of LLL translated from an old Modula-2 code.

Real	getMinLength2 ()
	Returns the square Euclidean length of the current shortest basis vector in the lattice.

Real	getMinLength ()
	Returns the length of the current shortest basis vector in the lattice, which is stored in a local variable.

Real	getMaxLength ()
	Returns the length of the current last basis vector in the lattice.

void	setBoundL2 (const RealVec &thresholds, int64_t dim1, int64_t dim2)
	Sets a vector of bounds on the square of the acceptable shortest vector lengths (for the Euclidean norm), in dimensions from `dim1+1` to `dim2`.

void	setIntLattice (IntLattice< Int, Real > &lat)
	Sets to `lat` the `IntLattice` object on which this reducer object will be working.

IntLattice< Int, Real > *	getIntLattice ()
	Returns the IntLattice object that this object is working on.

void	setDecompTypeBB (DecompTypeBB decomp)
	Sets the decomposition method used by this reduced to compute bounds in the BB procedures.

Public Attributes
int64_t	maxNodesBB = 10000000
	The maximum number of nodes in the branch-and-bound tree when calling `shortestVector` or `reductMinkowski`.

Detailed Description

template<typename Int, typename Real>
class LatticeTester::ReducerBB< Int, Real >

This ReducerBB class provides facilities to reduce the basis of a lattice (an IntLattice object) in various ways (pairwise, LLL, BKZ, Minkowski [4], [9], [10]), and to find a shortest nonzero vector in the lattice using a BB algorithm [rFIN85a].

Each Reducer must have an internal IntLattice object which is given upon construction and can also be changed later via setIntLattice. The reduction methods are applied to this internal object.

The shortestVector and reductMinkowski methods do not apply any pre-reduction by themselves Before calling them, one should always reduce the basis separately beforehand with an LLL or BKZ reduction, because it drastically reduces the size of the BB search. These two methods have no static version. To use them one must create Reducer object, which maintains several internal variables, vectors, and matrices. The recommended way is to create a single Reducer object with a maximal dimension large enough, and then call the shortestVector and reductMinkowski methods with the relevant IntLattice object as a parameter. ***** In fact, it can be always the same IntLattice object all the time!!! ***** The norm type, dimension, basis, vector lengths, etc. will be taken from this IntLattice object. The dimensions of the internal vectors and matrices can be larger than required; the methods will use only the entries that are needed for the given IntLattice basis. Creating a new Reducer object for each IntLattice that we want to handle is very inefficient and should be avoided, especially when we want to examine several projections for several lattices.

Most of the methods do not use or change the m-dual lattice. To reduce the m-dual basis or find a shortest nonzero vector in it, one should first dualize the lattice (IntLattice::dualize does that) and then apply the desired methods.