LatticeTester::BasisConstruction< BasInt > Class Template Reference

This class implements general methods to perform a lattice basis construction from a set of vectors, as well as general methods to obtain the dual lattice basis depending on the current lattice basis. More...

#include <latticetester/BasisConstruction.h>

Public Member Functions
void	LLLConstruction (BasIntMat &matrix)
	This functions takes a set of generating vectors of a vector space and finds a basis for this space whilst applying LLL reduction. More...
void	GCDConstruction (BasIntMat &matrix)
	This function does some kind of Gaussian elimination on \(\text{span}(\text{matrix}^t)\) as a vector space on \(\mathbb{Z}\) to obtain a basis of this vector space (lattice). More...
void	DualConstruction (BasIntMat &matrix, BasIntMat &dualMatrix, BasInt modulo)
	This method builds the dual of matrix in dualMatrix and multiplies modulo by the rescaling factor used. More...
void	DualSlow (BasIntMat &matrix, BasIntMat &dualMatrix, BasInt &modulo)
	This does the same thing as DualConstruction(), but is much slower. More...
template<typename Int , typename Dbl , typename RedDbl >
void	ProjectionConstruction (IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &in, IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &out, const Coordinates &proj)
	This is a method that does the general construction of the projection proj of the basis in and puts it in out. More...

Detailed Description

template<typename BasInt>
class LatticeTester::BasisConstruction< BasInt >

This class implements general methods to perform a lattice basis construction from a set of vectors, as well as general methods to obtain the dual lattice basis depending on the current lattice basis.

This module only works with NTL matrices because those are objects aware of their shape.

What is done here seems like very simple linear algebra BUT it is not. The fact that we operate only on the ring of integers makes it so that these simple algorithms can become way too slow very rapidly because the numbers they manipulate grow very fast. This also means that in many cases the usage of standard long type integers will overflow.

A note on basis construction

Although basis construction is mathematically simple (and also computationnally simple when in the field of real numbers), things can get messy. In higher dimensions (~30), the coefficients in the matrix start getting really big ( \(\gg 2^{64}\)) and needing a lot of memory (run the BasisConstruction example and see this for yourself). Therefore, we give users a few tips about the usage of this module.

• Prefer the usage of NTL types when using this module. The functions don't have any kind of overflow detection.
• Reduce the basis before doing a triangularization. Reducing a basis with LLL is much faster than GCDConstruction and seems to make this operation easier to perform.
• Use specialized methods. With a more in depth knowledge of your problem, it is possible that there are much more efficient ways to build a basis and its dual (and/or that those matrices will already be triangular).

Member Function Documentation

DualConstruction()

template<typename BasInt >

void LatticeTester::BasisConstruction< BasInt >::DualConstruction	(	BasIntMat &	matrix,
		BasIntMat &	dualMatrix,
		BasInt	modulo
	)

This method builds the dual of matrix in dualMatrix and multiplies modulo by the rescaling factor used.

This function uses the clever method developed in [5] that notes that for B to be a m-dual to A, we have to have that \(AB^t = mI\). It is quite easy to show that, knowing A is upper triangular, B will be a lower triangular matrix with A(i,i)*B(i,i) = m for all i and \( A_i \cdot B_j = 0\) for \(i\neq j\). And that to get the second condition, we simply have to recursively take for each line

\[B_{i,j} = -\frac{1}{A_{j,j}}\sum_{k=j+1}^i A_{j,k} B_{i,k}.\]

This does the computation much faster than doing a traditional solving of a linear system.

DualSlow()

template<typename BasInt >

void LatticeTester::BasisConstruction< BasInt >::DualSlow	(	BasIntMat &	matrix,
		BasIntMat &	dualMatrix,
		BasInt &	modulo
	)

This does the same thing as DualConstruction(), but is much slower.

This algorithm calculates the dual as well as the m used for rescalling.

This is here simply for the sake of comparison and should not be used in practice.

Suppose the basis matrix contains basis vectors on its lines and is \(p\times q\) where \(q \geq p\). We can compute the \(m\)-dual as follows. Let's note the basis matrix V and the dual matrix W and have lines of W also contain dual basis vectors in its lines. We know that \(VW^t = mI_{p\times p}\) where \(I\) is the identity matrix. Now, in the case of a \(m\)-dual computation, we can assume that all the arithmetic is done modulo \(m\) and that \(m\) is prime??

It checks if this m divides the modulo given to the algorithm. Right now, this assumes the basis is triangular, might need to change it.

GCDConstruction()

template<typename BasInt >

void LatticeTester::BasisConstruction< BasInt >::GCDConstruction

(

BasIntMat &

matrix

)

This function does some kind of Gaussian elimination on \(\text{span}(\text{matrix}^t)\) as a vector space on \(\mathbb{Z}\) to obtain a basis of this vector space (lattice).

This takes a matrix matrix where each row v[0], ..., v[n] is considered as a vector. This basically performs, for each column, Euclid's algorithm on the rows under the diagonal to set all coefficients to zero except the one in the diagonal. Finding the GCD of all the coefficients from the diagonal and under allows to perform Gaussian elimination using only the 3 allowed operations that do not change the span of the vectors:

• Multiply a line by \(-1\),
• Add an integer multiple of line \(i\) to line \(j\) for \(i \neq j\),
• Swap line \(i\) and line \(j\). After constructing this basis, the algorithm eliminates negative coefficients in the matrix.

WATCH OUT. This function (and building mecanism) are very memory heavy has the numbers below the diagonal can grow very big.

LLLConstruction()

template<typename BasInt >

void LatticeTester::BasisConstruction< BasInt >::LLLConstruction

(

BasIntMat &

matrix

)

This functions takes a set of generating vectors of a vector space and finds a basis for this space whilst applying LLL reduction.

This is much faster than applying GCDConstruction, but it doesn't help building the dual.

ProjectionConstruction()

template<typename BasInt >

template<typename Int , typename Dbl , typename RedDbl >

void LatticeTester::BasisConstruction< BasInt >::ProjectionConstruction	(	IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &	in,
		IntLatticeBasis< Int, BasInt, Dbl, RedDbl > &	out,
		const Coordinates &	proj
	)

This is a method that does the general construction of the projection proj of the basis in and puts it in out.

This will completely overwrite the lattice basis in out, changing the dimension. If one wants to compute the dual for this projection, it has to be done afterwards with the DualConstruction() method.

---

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

• include/latticetester/BasisConstruction.h