-
Available on Github
- Generated on Tue Jun 11 2019 15:21:28 for Lattice Tester Guide by
1.8.15
|
Lattice Tester Guide
1.0-9
Software Package For Testing The Uniformity Of Integral Lattices In The Real Space
|
This class implements (or wraps from NTL) all the functions that are needed to reduce a basis. More...
#include <latticetester/Reducer.h>
Public Member Functions | |
| Reducer (IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &lat) | |
Constructor that initializes the reducer to work on lattice basis lat. More... | |
| Reducer (const Reducer< Int, BasInt, Dbl, RedDbl > &red) | |
| Copy constructor. More... | |
| ~Reducer () | |
| Destructor. More... | |
| Reducer< Int, BasInt, Dbl, RedDbl > & | operator= (const Reducer< Int, BasInt, Dbl, RedDbl > &red) |
Assignment operator that allows copying red into the object by usig copy. More... | |
| void | copy (const Reducer< Int, BasInt, Dbl, RedDbl > &red) |
Copies the reducer red into this object. More... | |
| bool | shortestVector (NormType norm) |
Computes the shortest non-zero vector of the IntLatticeBasis stored in this object with respect to norm norm using branch-and-bound and the algorithm described in [13]. More... | |
| void | redDieter (int d, bool xx[]=NULL) |
This method performs pairwise reduction sequentially on all vectors of the basis whose indice is greater of equal to d. More... | |
| void | redDieterRandomized (int d, int seed) |
| This method does the same thing as redDieter(int) but the choice of vectors on which to perform pairwise reduction is randomized. More... | |
| void | redLLL (double fact=0.999999, std::int64_t maxcpt=1000000000, int dim=0) |
Performs a LLL (Lenstra-Lenstra-Lovasz) basis reduction for the first dim vector of the basis with coefficient fact. More... | |
| void | redLLLNTL (double fact=0.999999, PrecisionType precision=QUADRUPLE, int dim=0) |
| This is the NTL implementation of the floating point version of the LLL reduction algorithm presented in [22]. More... | |
| void | redLLLNTLExact (double fact) |
| This implements an algorithm to perform the original LLL reduction. More... | |
| void | redBKZ (double fact=0.999999, std::int64_t blocksize=10, PrecisionType precision=QUADRUPLE, int dim=0) |
| This is the NTL implementation of the floating point version of the BKZ reduction algorithm presented in [22]. 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... | |
| Dbl | getMinLength () |
| Returns the length of the shortest basis vector in the lattice. More... | |
| Dbl | getMaxLength () |
| Returns the length of the longest basis vector in the lattice. More... | |
| void | setBoundL2 (const DblVec &V, int dim1, int dim2) |
Sets a bound on the square length of the shortest vector in the lattice in dimensions from dim1+1 to dim2. More... | |
| IntLatticeBasis< Int, BasInt, Dbl, RedDbl > * | getIntLatticeBasis () |
| Returns the basis of this object is working on. More... | |
Static Public Attributes | |
| static std::int64_t | maxNodesBB = 1000000000 |
The maximum number of nodes in the branch-and-bound tree when calling ShortestVector or reductMinkowski. More... | |
Pre-reduction flags | |
Marc-Antoine: it is very possible that we can remove those variables. We just have to make sure that reductMinkowski does not need them These boolean variables indicate which type of pre-reduction is to be performed for | |
| static bool | PreRedDieterSV = false |
| static bool | PreRedLLLSV = false |
| static bool | PreRedLLLRM = false |
| static bool | PreRedBKZ = true |
This class implements (or wraps from NTL) all the functions that are needed to reduce a basis.
For a given lattice basis, stored in an IntLatticeBasis, this class can reduce it in the sense of Minkowski, as well as find the shortest vector in the lattice with the Branch-and-Bound algorithm. It is also possible to use weaker, but much faster, reductions such as pairwise-reduction [6], LLL reduction [17] and BKZ reduction [22]. The theoretical details of these algorithm are presented in Background.
Unless using Dieter or Minkowski reduction, the methods of this class do not change the dual of the lattice that is being reduced.
The LLL reduction has been implemented both by us and in NTL, but since we did not test our algorithm for efficiency, it is recommended to stick with the NTL implementation wrapped by the methods redLLLNTL and redLLLNTLExact. Note that redBKZ is also a wrapper for NTL algorithm for BKZ reduction.
To use this class, it suffices to create an instance of it by passing a IntLatticeBasis to the constructor. You can then simply call the methods and the IntLatticeBasis passed to the Reducer will be modified since it is stored as a pointer. You should note that the methods to compute the shortest vector apply no pre-reduction. In a real context, you should always reduce the basis separately with LLL or BKZ reduction before searching for the shortest vector since it drastically reduces the size of the branch-and-bound search.
| LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::Reducer | ( | IntLatticeBasis< Int, BasInt, Dbl, RedDbl > & | lat | ) |
Constructor that initializes the reducer to work on lattice basis lat.
| LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::Reducer | ( | const Reducer< Int, BasInt, Dbl, RedDbl > & | red | ) |
Copy constructor.
| LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::~Reducer | ( | ) |
Destructor.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::copy | ( | const Reducer< Int, BasInt, Dbl, RedDbl > & | red | ) |
Copies the reducer red into this object.
|
inline |
Returns the basis of this object is working on.
|
inline |
Returns the length of the longest basis vector in the lattice.
|
inline |
Returns the length of the shortest basis vector in the lattice.
| Reducer< Int, BasInt, Dbl, RedDbl > & LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::operator= | ( | const Reducer< Int, BasInt, Dbl, RedDbl > & | red | ) |
Assignment operator that allows copying red into the object by usig copy.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redBKZ | ( | double | fact = 0.999999, |
| std::int64_t | blocksize = 10, |
||
| PrecisionType | precision = QUADRUPLE, |
||
| int | dim = 0 |
||
| ) |
This is the NTL implementation of the floating point version of the BKZ reduction algorithm presented in [22].
1/2 < fact < 1 is a number that specifies the strenght of the condition on the basis, closer to 1 meaning a stronger condition. precision specifies the size of the floating point numbers the algorithm will use. Const.h provides a list of the possible values, but their description is done in the module LLL of NTL. dim is the number of vectors on which to apply the reduction with zero being the entire basis. blocksize is the size of the blocks of the reduction in the BKZ reduction condition. Roughly, larger blocks mean a stronger condition. A blocksize of 2 is equivalent to LLL reduction.
There should not really be a reason to change the default parameters suggested in this function. It is nonetheless possible to be in a situation where they do not work. In the occurence of poor quality results, it might be necessary to choose a better precision. Also, in a few rare cases, it is possible that fact be "too close to 1" and that the algorithm takes too much time. A user whishing to get a faster execution at the cost of condition strenght could also choose a smaller blocksize.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redDieter | ( | int | d, |
| bool | xx[] = NULL |
||
| ) |
This method performs pairwise reduction sequentially on all vectors of the basis whose indice is greater of equal to d.
xx[] is used internally when doing Minkowski reduction. This is somewhat ugly but this fixes a leak.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redDieterRandomized | ( | int | d, |
| int | seed | ||
| ) |
This method does the same thing as redDieter(int) but the choice of vectors on which to perform pairwise reduction is randomized.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLL | ( | double | fact = 0.999999, |
| std::int64_t | maxcpt = 1000000000, |
||
| int | dim = 0 |
||
| ) |
Performs a LLL (Lenstra-Lenstra-Lovasz) basis reduction for the first dim vector of the basis with coefficient fact.
fact is a floating point number between 1/2 and 1 that specifies the algorithm's tolerance to floating point arithmetic error. If fact is closer to 1, the basis will be (typically) "more reduced" as the algorithm will enforce a tighter condition on the basis, but that will require more work. The reduction algorithm is applied until maxcpt successful transformations have been done, or until the basis is correctly reduced.
This algorithm is an implementation of the LLL reduction algorithm made in our lab. It is considerably slower than what is available through NTL for NTL types, but performs well on standard C++ types. This implementation always uses the Euclidean norm.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLLNTL | ( | double | fact = 0.999999, |
| PrecisionType | precision = QUADRUPLE, |
||
| int | dim = 0 |
||
| ) |
This is the NTL implementation of the floating point version of the LLL reduction algorithm presented in [22].
1/2 < fact < 1 is a number that specifies the strenght of the condition on the basis, closer to 1 meaning a stronger condition. precision specifies the size of the floating point numbers the algorithm will use. Const.h provides a list of the possible values, but their description is done in the module LLL of NTL. dim is the number of vectors on which to apply the reduction (zero being the entire basis).
There should not really be a reason to change the default parameters suggested in this function. It is nonetheless possible to be in a situation where they do not work. In the occurence of poor quality results, it might be necessary to choose a better precision. Also, in a few rare cases, it is possible that fact be "too close to 1" and that the algorithm takes too much time.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLLNTLExact | ( | double | fact | ) |
This implements an algorithm to perform the original LLL reduction.
| bool LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::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[0] and the std::int64_test is V[Dim-1]).
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::setBoundL2 | ( | const DblVec & | V, |
| int | dim1, | ||
| int | dim2 | ||
| ) |
Sets a bound on the square length of the shortest vector in the lattice in dimensions from dim1+1 to dim2.
V[i] has to contain a lower bound on the square of the lenght of the shortest vector in the lattice in dimension i+1. Such a bound, if it is set, will be used during during the Branch-and-Bound step when searching the sortest vector of a lattice. If the Branch-and-Bound proves that the shortest vector of the lattice is smaller than the bound, the algorithm will stop. This is usefull in the case where the user is searching for a good lattice with the spectral test since this can cut off some work.
| bool LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::shortestVector | ( | NormType | norm | ) |
Computes the shortest non-zero vector of the IntLatticeBasis stored in this object with respect to norm norm using branch-and-bound and the algorithm described in [13].
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. If the reduction was successful, the new reduced basis can be accessed as desired via getIntLatticeBasis().
It is strongly recommended to use some kind of pre-reduction before using this method. We suggest redLLLNTL that should be god for most use cases, but redBKZ can sometimes git better results. None of the Dieter pre-reduction should be called before calling this, unless the user's intention is to benchmark the different methods in his use case.
|
static |
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.8.15