- Generated on Fri Aug 17 2018 17:21:03 for LatNet Builder Manual by
1.8.14
|
LatNet Builder Manual
2.0.1-11
Software Package for Constructing Highly Uniform Point Sets
|
This class implements (or wraps from NTL) all the functions that are needed to reduce a basis. More...
#include <Reducer.h>
Public Member Functions | |
| Reducer (IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &lat) | |
Constructor that initializes the reducer to work on lattice basis lat. | |
| Reducer (const Reducer< Int, BasInt, Dbl, RedDbl > &red) | |
| Copy constructor. | |
| ~Reducer () | |
| Destructor. | |
| 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 | copy (const Reducer< Int, BasInt, Dbl, RedDbl > &red) |
Copies the reducer red into this object. | |
| 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 [16]. More... | |
| void | redDieter (int d) |
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, std::int64_t maxcpt, int dim) |
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 [28]. More... | |
| void | redLLLNTLExact (double fact) |
| Marc-Antoine: I do not think what is stated bellow is exact. 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 [28]. 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. | |
| Dbl | getMaxLength () |
| Returns the length of the longest basis vector in the lattice. | |
| 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. | |
Static Public Attributes | |
| static std::int64_t | maxNodesBB = 10000000 |
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 (in fact I think reductMinkowski has to be reviewed). 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 Dieter reduction [9], LLL reduction [22] and BKZ reduction [28]. The theoretical details of these algorithm are presented in a_intro.
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 reduces drastically the size of the branch-and-bound search.
| 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 [28].
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). 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.
Referenced by LatticeTester::ShortestVector().
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redDieter | ( | int | d | ) |
This method performs pairwise reduction sequentially on all vectors of the basis whose indice is greater of equal to d.
Normalement, cette méthode devrait implémenter l'algorithme de Dieter en se basant sur Knuth, mais là ça ne fait que de réductions par paires et ça arrête après un certain nombre d'itérations qui ne font rien. Il faudrait vérifier que soit : c'est parfaitement ce que l'algorithme fait ou bien sinon il faudrait changer cet algorithme pour faire la bonne chose.
| 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.
On a le même problème que dans redDieter, c'est-à-dire que ce n'est pas clair que ça fait exactement l'algorithme que l'on dit que ça fait dans la doc.
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLL | ( | double | fact, |
| std::int64_t | maxcpt, | ||
| int | dim | ||
| ) |
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/4(?) and 1 that specifies the algorithm's tolerance to floating point arithmetic error. has to be between 1/2 and 1. 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 not recommended to use it because it has not been tested extensively for distribution. Instead, it is recommended to use (in the case that you wanted to use the LLL reduction algorithm) the redLLLNTL method. 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 [28].
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.
Referenced by LatticeTester::ShortestVector().
| void LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLLNTLExact | ( | double | fact | ) |
| 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]).
Referenced by LatticeTester::MinkowskiReduction().
| 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 [16].
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.
Referenced by LatticeTester::ShortestVector().
|
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.14