This class provides tools to calculate the figure of merit (FOM) \( M_{t_1,\dots,t_d}\) for any given IntLatticeExt object. More...

Inheritance diagram for LatticeTester::FigureOfMeritM< Int, Real >:

Public Member Functions
	FigureOfMeritM (const NTL::Vec< int64_t > &t, Weights &w, Normalizer &norma, ReducerBB< Int, Real > *red=0, bool includeFirst=false)
	This constructor will call `setTVector (t, includeFirst)`, then set the 'Weights', `Normalizer`, and `ReducerBB` to the given values.

virtual	~FigureOfMeritM ()

void	setTVector (const NTL::Vec< int64_t > &t, bool includeFirst)
	Sets the vector \((t_1,..., t_d)\) in the FOM definition to the vector `t`.

void	setWeights (Weights &w)
	Sets the weights used for calculating the FoM.

void	setNormalizer (Normalizer &norma)
	Sets the normalizer to `norma`.

void	setLLL (double delta=0.99999)
	Sets the parameters for the LLL reduction.

void	setBKZ (double delta=0.99999, int64_t blocksize=10)
	Sets the parameters for the BKZ reduction.

void	setBB (bool redBB)
	The BB method will be applied iff this flag is set to true (the default value).

void	setReducerBB (ReducerBB< Int, Real > *red)
	Sets the `ReducerBB` object that will be used for BB.

void	setLowBound (double low)
	Sets the low bound for the FOM.

void	setVerbosity (int64_t verbose)
	The level of verbosity in the terminal output.

void	setCollectLevel (int64_t collect)
	The level of details in the informations that are collected, such as the worst-case projection, the corresponding shortest vector, its square length, etc.

double	getMinMeritSqlen ()
	Returns the square length of the shortest vector for the worst-case projection.

Coordinates	getMinMeritProj ()
	Returns the projection that gives the worst merit value.

double	computeMeritOneProj (IntLattice< Int, Real > &proj, const Coordinates &coord, double minmerit=DBL_MAX)
	This function computes and returns the merit value for a single projection represented in lattice `proj`, in `dim` dimensions.

virtual double	computeMeritSucc (IntLatticeExt< Int, Real > &lat, double minmerit=DBL_MAX)
	This function computes and returns the FOM only for the projections over sets of successive coordinates of the form {1, 2, ..., m_t.length()} to {1, 2, ..., m_t[0]}, and returns the minimum.

virtual double	computeMeritNonSucc (IntLatticeExt< Int, Real > &lat, IntLattice< Int, Real > &proj, double minmerit=DBL_MAX)
	This function computes and returns the FOM only for the projections over sets on non-successive coordinates determined by \(S(s,t_s)\) or \(S^{(1)}(s,t_s)\).

double	computeMerit (IntLatticeExt< Int, Real > &lat, IntLattice< Int, Real > &proj, double minmerit=DBL_MAX)
	This function computes and returns the value of the FOM for the given lattice 'lat', using the norm associated with that lattice.

Protected Attributes
NTL::Vec< int64_t >	m_t

int64_t	m_tsize = 0

Weights *	m_weights

Normalizer *	m_norma

double	m_deltaLLL = 0.0

double	m_deltaBKZ = 0.99999

int64_t	m_blocksizeBKZ = 10

bool	m_redBB = true

CoordinateSets::FromRanges *	m_coordRange

ReducerBB< Int, Real > *	m_red

NTL::Vec< Real >	m_sqlen

bool	m_includeFirst = false

double	m_lowbound = 0.0

double	m_minMerit = DBL_MAX

double	m_minMeritSqlen = 0

Coordinates	m_minMeritProj

Coordinates	m_worstproj

int64_t	m_verbose = 0

int64_t	m_collectLevel = 0

Detailed Description

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

This class provides tools to calculate the figure of merit (FOM) \( M_{t_1,\dots,t_d}\) for any given IntLatticeExt object.

This FOM is defined as

\[ M_{t_1,\dots,t_d} = \min\left[ \min_{I\in S(t_1)} \frac{\ell_I}{ \omega_I\, \ell_I^*(\eta_I)},\; \min_{2\le s\le d}\, \min_{I\in S(s,t_s)} \frac{\ell_I}{\omega_I \,\ell_I^*(\eta_I)} \right]. \]

In this class, it is computed for the (rescaled) primal lattice and the m-dual is never used. To compute the FOM for the m-dual, see the class FigureOfMeritMDual. Just using the present class for the dualized primal lattice object will not give correct results, because the projections of the m-dual lattice are not the same as the m-duals of the projections.

In the formula, the projections in \(S(t_1)\) are those over successive coordinates in up to \(t_1\) dimensions, while those is \(S(s,t_s)\) are projections over \(s\) distinct coordinates that are non necessarily successive and are all in the set \(\{1,\dots,t_s\}\), for each order \(s > 1\). There are two variants for the latter: the first (default) variant takes \(S(s,t_s)\) as just defined, and the other considers only the set \(S^{(1)}(s,t_s)\) of projections that contain coordinate 1. The parameter includeFirst in the constructor determines which variant is taken: the latter option is taken when includeFirst is set to true. See the guide for more details and examples.

The lengths of the shortest vectors in the projections can be calculated exactly by using the BB algorithm after applying pre-reductions such as LLL or BKZ, or they can be just approximated by the lengths of the shortest basis vector after applying the pre-reductions only. The latter is faster but may not give a shortest vector. The norm used to compute the vector lengths is always the one inside the IntLattice object for which we compute the FOM.

The constructor has two template parameters to specify which Int and Real types are used. It also requires the vector \((t_1,\dots,t_d)\), a Weights object to specify the weights \(\omega_I\), a Normalizer object used to normalize the merit values, a ReducerBB object used for the reduction in case we want to apply BB, and the includeFirst parameter in case we want to change it to true. The last two parameters are optional. The BB is applied if and only if a (nonzero) ReducerBB is given. Otherwise, we just use static methods for the reduction and need no Reducer. By default, the pre-reduction method is BKZ with delta = 0.99999 and blocksize = 10. To change these values and/or apply LLL, one can use setBKZ and/or setLLL. The reductions are always applied in the order: LLL, BKZ, BB. To remove LLL or BKZ, it suffices to set its delta parameter to 0.0.

After a FigureOfMeritM has been created by the constructor, one can use setTVector to set (or reset) the vector \((t_1,\dots,t_d)\), setWeights to change the weights, setLLL or setBKZ to change the LLL or BKZ parameters, etc.

The method computeMerit computes the FOM for a given lattice. The computation is stopped (early exit) as soon as we know that the value of the FOM will be below the lower bound, whose value can be changed via setLowBound. The default value is 0.

Constructor & Destructor Documentation

◆ FigureOfMeritM()

template<typename Int , typename Real >

LatticeTester::FigureOfMeritM< Int, Real >::FigureOfMeritM	(	const NTL::Vec< int64_t > &	t,
		Weights &	w,
		Normalizer &	norma,
		ReducerBB< Int, Real > *	red = 0,
		bool	includeFirst = false )

This constructor will call setTVector (t, includeFirst), then set the 'Weights', Normalizer, and ReducerBB to the given values.

◆ ~FigureOfMeritM()

template<typename Int , typename Real >

LatticeTester::FigureOfMeritM< Int, Real >::~FigureOfMeritM ( )

virtual

Member Function Documentation

◆ setTVector()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setTVector	(	const NTL::Vec< int64_t > &	t,
		bool	includeFirst )

Sets the vector \((t_1,..., t_d)\) in the FOM definition to the vector t.

Note that the values of \(t_1,..., t_d\) are taken from t[0],...,t[d-1], respectively. When includeFirst is true, we consider only the non-successive projections that contain coordinate 1. See the doc of the class FromRanges in CoordinateSets for more details.

◆ setWeights()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setWeights ( Weights & w )

inline

Sets the weights used for calculating the FoM.

◆ setNormalizer()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setNormalizer ( Normalizer & norma )

inline

Sets the normalizer to norma.

◆ setLLL()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setLLL ( double delta = 0.99999 )

inline

Sets the parameters for the LLL reduction.

If delta = 0, LLL is not applied.

◆ setBKZ()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setBKZ	(	double	delta = 0.99999,
		int64_t	blocksize = 10 )

inline

Sets the parameters for the BKZ reduction.

If delta = 0, BKZ is not applied.

◆ setBB()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setBB ( bool redBB )

inline

The BB method will be applied iff this flag is set to true (the default value).

◆ setReducerBB()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setReducerBB ( ReducerBB< Int, Real > * red )

inline

Sets the ReducerBB object that will be used for BB.

◆ setLowBound()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setLowBound ( double low )

inline

Sets the low bound for the FOM.

The FOM computation is stopped as soon as we know it is below this bound. The default value is 0.

◆ setVerbosity()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setVerbosity ( int64_t verbose )

inline

The level of verbosity in the terminal output.

The default value is 0 (minimal output). Values from 1 to 4 give increasingly more details.

◆ setCollectLevel()

template<typename Int , typename Real >

void LatticeTester::FigureOfMeritM< Int, Real >::setCollectLevel ( int64_t collect )

inline

The level of details in the informations that are collected, such as the worst-case projection, the corresponding shortest vector, its square length, etc.

The default value is 0 (minimal information, only the FOM). With values from 1 to 4, we collect increasingly more details.

◆ getMinMeritSqlen()

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::getMinMeritSqlen ( )

inline

Returns the square length of the shortest vector for the worst-case projection.

The returned value is valid only if the collection level was at least 1.

◆ getMinMeritProj()

template<typename Int , typename Real >

Coordinates LatticeTester::FigureOfMeritM< Int, Real >::getMinMeritProj ( )

inline

Returns the projection that gives the worst merit value.

The returned value is valid only if the collection level was at least 1.

◆ computeMeritOneProj()

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritOneProj	(	IntLattice< Int, Real > &	proj,
		const Coordinates &	coord,
		double	minmerit = DBL_MAX )

This function computes and returns the merit value for a single projection represented in lattice proj, in dim dimensions.

It returns 0 if the computation is not completed for any reason.

◆ computeMeritSucc()

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritSucc	(	IntLatticeExt< Int, Real > &	lat,
		double	minmerit = DBL_MAX )

virtual

This function computes and returns the FOM only for the projections over sets of successive coordinates of the form {1, 2, ..., m_t.length()} to {1, 2, ..., m_t[0]}, and returns the minimum.

It returns 0 if the computation was not completed for some reason.

Reimplemented in LatticeTester::FigureOfMeritDualM< Int, Real >.

◆ computeMeritNonSucc()

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritNonSucc	(	IntLatticeExt< Int, Real > &	lat,
		IntLattice< Int, Real > &	proj,
		double	minmerit = DBL_MAX )

virtual

This function computes and returns the FOM only for the projections over sets on non-successive coordinates determined by \(S(s,t_s)\) or \(S^{(1)}(s,t_s)\).

It returns 0 if the computation was not completed for some reason. The parameter proj is like for computeMerit.

Reimplemented in LatticeTester::FigureOfMeritDualM< Int, Real >.

◆ computeMerit()

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::computeMerit	(	IntLatticeExt< Int, Real > &	lat,
		IntLattice< Int, Real > &	proj,
		double	minmerit = DBL_MAX )

This function computes and returns the value of the FOM for the given lattice 'lat', using the norm associated with that lattice.

The function returns 0 if the computation was not completed for some reason (early exit, error, etc.). The parameter proj points to a secondary IntLattice object used to store the projections when computing the FOM. The maxDim in this object must be large enough so it can store any of the projections: maxDim \(\ge \max(s,t_1)\). Re-using this object permits one to avoid creating new objects internally. We need a full IntLattice object (not only a basis) for when we apply BB to the projection.

Member Data Documentation

◆ m_t

template<typename Int , typename Real >

NTL::Vec<int64_t> LatticeTester::FigureOfMeritM< Int, Real >::m_t

protected

◆ m_tsize

template<typename Int , typename Real >

int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_tsize = 0

protected

◆ m_weights

template<typename Int , typename Real >

Weights* LatticeTester::FigureOfMeritM< Int, Real >::m_weights

protected

◆ m_norma

template<typename Int , typename Real >

Normalizer* LatticeTester::FigureOfMeritM< Int, Real >::m_norma

protected

◆ m_deltaLLL

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::m_deltaLLL = 0.0

protected

◆ m_deltaBKZ

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::m_deltaBKZ = 0.99999

protected

◆ m_blocksizeBKZ

template<typename Int , typename Real >

int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_blocksizeBKZ = 10

protected

◆ m_redBB

template<typename Int , typename Real >

bool LatticeTester::FigureOfMeritM< Int, Real >::m_redBB = true

protected

◆ m_coordRange

template<typename Int , typename Real >

CoordinateSets::FromRanges* LatticeTester::FigureOfMeritM< Int, Real >::m_coordRange

protected

◆ m_red

template<typename Int , typename Real >

ReducerBB<Int, Real>* LatticeTester::FigureOfMeritM< Int, Real >::m_red

protected

◆ m_sqlen

template<typename Int , typename Real >

NTL::Vec<Real> LatticeTester::FigureOfMeritM< Int, Real >::m_sqlen

protected

◆ m_includeFirst

template<typename Int , typename Real >

bool LatticeTester::FigureOfMeritM< Int, Real >::m_includeFirst = false

protected

◆ m_lowbound

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::m_lowbound = 0.0

protected

◆ m_minMerit

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::m_minMerit = DBL_MAX

protected

◆ m_minMeritSqlen

template<typename Int , typename Real >

double LatticeTester::FigureOfMeritM< Int, Real >::m_minMeritSqlen = 0

protected

◆ m_minMeritProj

template<typename Int , typename Real >

Coordinates LatticeTester::FigureOfMeritM< Int, Real >::m_minMeritProj

protected

◆ m_worstproj

template<typename Int , typename Real >

Coordinates LatticeTester::FigureOfMeritM< Int, Real >::m_worstproj

protected

◆ m_verbose

template<typename Int , typename Real >

int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_verbose = 0

protected

◆ m_collectLevel

template<typename Int , typename Real >

int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_collectLevel = 0

protected

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

include/latticetester/FigureOfMeritM.h

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ FigureOfMeritM()

◆ ~FigureOfMeritM()

Member Function Documentation

◆ setTVector()

◆ setWeights()

◆ setNormalizer()

◆ setLLL()

◆ setBKZ()

◆ setBB()

◆ setReducerBB()

◆ setLowBound()

◆ setVerbosity()

◆ setCollectLevel()

◆ getMinMeritSqlen()

◆ getMinMeritProj()

◆ computeMeritOneProj()

◆ computeMeritSucc()

◆ computeMeritNonSucc()

◆ computeMerit()

Member Data Documentation

◆ m_t

◆ m_tsize

◆ m_weights

◆ m_norma

◆ m_deltaLLL

◆ m_deltaBKZ

◆ m_blocksizeBKZ

◆ m_redBB

◆ m_coordRange

◆ m_red

◆ m_sqlen

◆ m_includeFirst

◆ m_lowbound

◆ m_minMerit

◆ m_minMeritSqlen

◆ m_minMeritProj

◆ m_worstproj

◆ m_verbose

◆ m_collectLevel