-
Available on Github
- Generated by
1.12.0
|
Lattice Tester Online Documentation unknown
Software Package For Testing The Uniformity Of Integral Lattices In The Real Space
|
This class provides functions to find a shortest nonzero vector in the lattice using a BB algorithm as in [4], and to compute a Minkowski basis reduction as in [1]. More...
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 () | |
| Destructor. | |
| bool | shortestVector () |
Computes a shortest non-zero vector for the IntLattice stored in this ReducerBB object, for the norm stored in this IntLattice, using the BB algorithm described in [5] 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. | |
| IntVec | getShortVec () |
| Returns the current shortest vector found in this lattice. | |
| Real | getMinLength2 () |
| Returns the square length of the current shortest vector in the lattice, usually computed with the current norm. | |
| Real | getMinLength () |
| Returns the length (not squared) of the current shortest 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. | |
| int64_t | getCountNodes () |
| Returns the number of nodes that have been visited in the BB tree. | |
| int64_t | getCountLeaves () |
| Returns the number of leaves visited in the BB tree. | |
| int64_t | getMaxZj () |
Returns the maximal absolute value of a z_j in the latest BB. | |
| void | setBounds2 (const RealVec &thresholds, int64_t dim1, int64_t dim2) |
Sets a vector of bounds on the square of the acceptable shortest vector lengths, for each dimension 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. | |
| void | setVerbosity (int64_t verbose) |
| Sets the level of verbosity in the terminal output. | |
Public Attributes | |
| int64_t | maxNodesBB = 10000000 |
The maximum number of nodes in the branch-and-bound tree when calling shortestVector or reductMinkowski. | |
This class provides functions to find a shortest nonzero vector in the lattice using a BB algorithm as in [4], and to compute a Minkowski basis reduction as in [1].
Each ReducerBB has an internal IntLattice object given upon construction and modifiable via setIntLattice. The shortestVector and reductMinkowski functions are applied to this internal object and always use the norm associated with that IntLattice object. These functions do not apply any pre-reduction by themselves. Before calling them, one should always pre-reduce the basis via LLL or BKZ, because it drastically reduces the size of the BB search tree.
The ReducerBB object maintains several internal variables, vectors, and matrices used by the shortestVector and reductMinkowski functions. It is recommended to create a single ReducerBB object with a large enough maximal dimension and then call the main functions with the relevant IntLattice object as a parameter. One may also re-use the same IntLattice objects for many different lattices, for example when performing a search for a good lattice. The norm type, dimension, basis, vector lengths, etc. will be taken from this internal 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 ReducerBB 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.
The functions in this class do not use or change the m-dual lattice. To find a shortest nonzero vector in the m-dual lattice, one should dualize the lattice (IntLattice::dualize does that) and then apply the desired functions. For the m-dual lattice of a projection, one should take the m-dual of a basis for the projection.
| LatticeTester::ReducerBB< Int, Real >::ReducerBB | ( | IntLattice< Int, Real > & | lat | ) |
Constructor that initializes the reducer to work on the lattice lat.
The maximal dimension will be that of lat.
| LatticeTester::ReducerBB< Int, Real >::ReducerBB | ( | int64_t | maxDim | ) |
Constructor of a ReducerBB than can handle up to maxDim dimensions.
Space will be reserved once for all for the internal IntMat objects such as the Gram and Cholesky matrices. These same matrices will be re-used over and over to avoid repeated space reallocation. It is recommended to create a reducer with a large enough max dim in the first place, using this constructor.
| LatticeTester::ReducerBB< Int, Real >::~ReducerBB | ( | ) |
Destructor.
| bool LatticeTester::ReducerBB< Int, Real >::shortestVector | ( | ) |
Computes a shortest non-zero vector for the IntLattice stored in this ReducerBB object, for the norm stored in this IntLattice, using the BB algorithm described in [5] and [7].
The admissible norm types are L1NORM and L2NORM (see EnumTypes.h). If the constant ReducerBB::MaxNodesBB (see below) is exceeded during the branch-and-bound, the method aborts and returns false. Otherwise, it returns true. If the reduction was successful, the new reduced basis can be accessed via getIntLattice(). The shortest vector is placed in first position and its norm is updated. The other vectors are not sorted.
This function uses only the basis of the internal lattice, its vector lengths, and scalar products. It never uses its m-dual. To compute a shortest vector in the m-dual, one must first call dualize on the target IntLattice object. It is strongly recommended to use redBKZ or redLLLNTL to pre-reduce the basis before invoking this method; this is not done automatically. It is assumed that getDim returns the correct dimension of the internal lattice.
| bool LatticeTester::ReducerBB< Int, Real >::shortestVector | ( | IntLattice< Int, Real > & | lat | ) |
In this version, the lattice is passed as a parameter.
It will become the new IntLattice of this ReducerBB object. This method calls setIntLattice(lat), so if the max dimension for the ReducerBB is not large enough for lat, all the internal variables of this reducer will be reset and the vectors and matrices will be automatically enlarged. In particular, the bounds set by setBounds2 have to be reset. If the max dimension is large enough, only a pointer is changed.
| bool LatticeTester::ReducerBB< Int, Real >::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.
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 increasing vector lengths. For a full reduction, just omit the d parameter.
| bool LatticeTester::ReducerBB< Int, Real >::reductMinkowski | ( | IntLattice< Int, Real > & | lat, |
| int64_t | d = 0 ) |
In this version, the lattice is passed as a parameter.
It will become the new IntLattice of this ReducerBB object, exactly as in shortestVector(IntLattice).
|
inline |
Returns the current shortest vector found in this lattice.
It is usually the first basis vector, but during the BB procedure it may happen that' this shortest vector is not in the basis.
|
inline |
Returns the square length of the current shortest vector in the lattice, usually computed with the current norm.
During the BB procedure, it may happen that this shortest vector is not yet in the basis.
|
inline |
Returns the length (not squared) of the current shortest vector in the lattice, which is stored in a local variable.
This depends only on the lattice, but this length is stored and used in this class.
|
inline |
Returns the length of the current last basis vector in the lattice.
|
inline |
Returns the number of nodes that have been visited in the BB tree.
|
inline |
Returns the number of leaves visited in the BB tree.
|
inline |
Returns the maximal absolute value of a z_j in the latest BB.
| void LatticeTester::ReducerBB< Int, Real >::setBounds2 | ( | const RealVec & | thresholds, |
| int64_t | dim1, | ||
| int64_t | dim2 ) |
Sets a vector of bounds on the square of the acceptable shortest vector lengths, for each dimension from dim1+1 to dim2.
For each i, thresholds[i] must contain a lower bound on the square length of the shortest lattice vector in dimension i+1, for the current norm. This bound will be used during during the Branch-and-Bound step when computing a shortest lattice vector. As soon as a vector shorter than the bound is found, the BB algorithm will stop. This is useful to reduce work when we search for a good lattice with the spectral test. If these bounds are not set, the default values of 0 are used. It is recommended to set these bounds before calling shortestVector for the first time when making searches for good lattices.
|
inline |
Sets to lat the IntLattice object on which this reducer object will be working.
If it is already lat, nothing is done. If the dimension of lat is larger than the max dimension for this ReducerBB, the latter is increased and the ReducerBB is re-initialized with new internal variables having the appropriate dimensions. Otherwise, the internal variables are left unchanged. It is recommended to create the reducer with a large enough max dim in the first place.
|
inline |
Returns the IntLattice object that this object is working on.
|
inline |
Sets the decomposition method used by this reduced to compute bounds in the BB procedures.
It can be CHOLESKY or TRIANGULAR.
|
inline |
Sets the level of verbosity in the terminal output.
The default value is 0 (minimal output). Values from 1 to 4 give increasingly more details.
| int64_t LatticeTester::ReducerBB< Int, Real >::maxNodesBB = 10000000 |
The maximum number of nodes in the branch-and-bound tree when calling shortestVector or reductMinkowski.
When this number is exceeded, the method aborts and returns false.
1.12.0