For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest non-zero vector of the lattice using pre-reductions and a branch-and-bound (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 non-zero vector of this lattice with respect to norm `norm` using branch-and-bound 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 branch-and-bound, in `reductMinkowski`.

bool	redBB0 (NormType norm)
	Tries to shorten the smallest vector of the primal basis using branch-and-bound, 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 non-zero vector using norm `norm`. More...

void	redLLL (double fact, long maxcpt, int dim)
	Performs a LLL (Lenstra-Lenstra-Lovasz) 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 branch-and-bound 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 branch-and-bound 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 branch-and-bound 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 branch-and-bound tree when calling `ShortestVector` or `reductMinkowski`. More...

static bool	PreRedDieterSV
	These boolean variables indicate which type of pre-reduction is to be performed for `ShortestVector` (SV) and for `reductMinkowski` (RM). More...

static bool	PreRedLLLSV

static bool	PreRedLLLRM

Detailed Description

For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest non-zero vector of the lattice using pre-reductions and a branch-and-bound (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.

Constructor & Destructor Documentation

LatCommon::Reducer::Reducer ( IntLattice & lat )

Constructor.

Initializes the reducer to work on lattice lat.

Member Function Documentation

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.

Note: Richard: Encore utile?

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 )

Finds the shortest non-zero vector using norm norm.

Does not modify the basis. Stops and returns false if not finished after examining possib. Returns true upon success., and returns length in Lmin. Uses the algorithm of Dieter [6] given in Knuth [10] .

void LatCommon::Reducer::redLLL	(	double	fact,
		long	maxcpt,
		int	dim
	)

Performs a LLL (Lenstra-Lenstra-Lovasz) 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 branch-and-bound 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 % (64-bit) floating-point representation. % In this sense, the results are not 100% reliable.

bool LatCommon::Reducer::shortestVector ( NormType norm )

Computes the shortest non-zero vector of this lattice with respect to norm norm using branch-and-bound 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 branch-and-bounds, the method aborts and returns false. Otherwise, it returns true. Uses the pre-reduction algorithms of Dieter and of Lenstra-Lenstra-Lovasz.

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\).

Member Data Documentation

const long LatCommon::Reducer::MAX_PRE_RED = 1000000

static

Maximum number of transformations in the method PreRedDieter.

After MAX_PRE_RED successful transformations have been performed, the prereduction is stopped.

long LatCommon::Reducer::maxNodesBB

static

The maximum number of nodes % that we are ready to accept in the branch-and-bound tree when calling ShortestVector or reductMinkowski.

When this number is exceeded, the method aborts and returns false.

bool LatCommon::Reducer::PreRedDieterSV

static

These boolean variables indicate which type of pre-reduction is to be performed for ShortestVector (SV) and for reductMinkowski (RM).

Dieter means the pairwise pre-reduction 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.

const long LatCommon::Reducer::SHORT_DIET = 1000

static

Whenever the number of nodes in the branch-and-bound 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.

const long LatCommon::Reducer::SHORT_LLL = 1000

static

Whenever the number of nodes in the branch-and-bound 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.

The documentation for this class was generated from the following file:

latcommon/include/latcommon/Reducer.h

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation