Lattice namespace. More...

Namespaces
namespace	CoordinateSets
	The classes `FromRange`, `SubSets`, and `AddCoordinate` are defined here.

namespace	Random
	This class generates random numbers (in fact pseudo-random numbers).

Classes
class	Chrono
	This class acts as an interface to the system clock to compute the CPU time used by parts of a program. More...

class	Coordinates
	This is basically a `std::set<std::size_t>`, i.e., a standard C++ set. More...

class	FigureOfMeritDualM
	This class offers funcitons to calculate the figure of merit (FOM) for the m-dual of any given 'IntLatticeExt' object. More...

class	FigureOfMeritM
	$\f, for each order $s > 1$. More...

class	FoMCalc
	This class offers methods (functions) to calculate figure of merit for a given IntLattice object. More...

class	IntLattice
	An `IntLattice` object is an integral lattice, with its basis or its `m`-dual basis, or both. More...

class	IntLatticeExt
	This abstract class extends `IntLattice` and is a skeleton for the specialized subclasses that define specific types of lattices. More...

class	Lacunary
	REMOVE! More...

class	MRGLattice
	This subclass of `IntLatticeExt` defines an MRG lattice and is similar to Rank1Lattice, but constructs lattices associated with multiple recursive generators (MRGs) with modulus m, order k, and vector of multipliers a = (a_1, . More...

class	NormaBestBound
	In this normalizer, the Hermite constants $\gamma_s$ are approximated using the best upper bounds that are available. More...

class	NormaBestLat
	This Normalizer class implements upper bounds on the length of the shortest nonzero vector in a lattice. More...

class	NormaLaminated
	This Normalizer class implements upper bounds on the length of the shortest nonzero vector in a lattice. More...

class	Normalizer
	This is a base class for implementing normalization constants used in figures of merit, to normalize the length of the shortest nonzero vector in either the primal or dual lattice. More...

class	NormaMinkL2
	This class implements Minkowski’s theoretical LOWER bound on the length of the shortest non-zero vector in a lattice, with the ${\mathcal{L}}_2$ norm. More...

class	NormaPalpha
	This class implements some theoretical bounds on the values of $P_{\alpha}$ for a lattice (see class `Palpha`). More...

class	NormaRogers
	This class implements upper bounds on the length of the shortest nonzero vector in a lattice, in which the Hermite constants $\gamma_s$ are approximated by their Rogers's bounds. More...

class	ParamReader
	Utility class that can be used to read different kind of data from a file. More...

class	Rank1Lattice
	This subclass of `IntLatticeExt` defines a general rank 1 lattice rule in $d$ dimensions, whose points $\mathbb{u}_i$ are defined by. More...

class	ReducerBB
	This `ReducerBB` class provides facilities to reduce the basis of a lattice (an `IntLattice` object) in various ways (pairwise, LLL, BKZ, Minkowski [4], [9], [10]), and to find a shortest nonzero vector in the lattice using a BB algorithm [rFIN85a]. More...

class	Types
	Sets standard `typedef`’s for the types that can be used in LatticeTester. More...

class	Weights
	Abstract class that defines an interface to specify Weights given to projections in figures of merit. More...

class	WeightsOrderDependent
	Defines order-dependent weights. More...

class	WeightsPOD
	Defines product and order-dependent (POD) weights. More...

class	WeightsProduct
	Defines product weights. More...

class	WeightsProjectionDependent
	Defines projection-dependent weights. More...

class	WeightsUniform
	Specifies projection weights that are the same (usually 1) for all projections. More...

class	Writer
	This is an abstract class that represents an interface to `Writer` classes. More...

class	WriterRes
	This class is a simple implementation of the `Writer` abstract class to write in plain text format on the stream. More...

Typedefs
typedef double	Weight
	A scalar weight type.

Enumerations
enum	NormType { SUPNORM , L1NORM , L2NORM , ZAREMBANORM }
	The available norm types to measure the length of vectors. More...

enum	OutputType { TERM , RES , TEX , GEN }
	Different choices of output formats. More...

enum	ProblemType { BASIS , DUAL , REDUCTION , SHORTEST , MERIT }
	Types of problems that LatticeTester can handle. More...

enum	PrecisionType { DOUBLE , QUADRUPLE , XDOUBLE , RR }
	This can be supersed by the Real type. More...

enum	PrimeType { PRIME , PROB_PRIME , COMPOSITE , UNKNOWN }
	Indicates whether an integer is prime, probably prime, composite or its status is unknown (or we do not care). More...

enum	CriterionType { LENGTH , SPECTRAL , BEYER , PALPHA , BOUND_JS }
	Merit criteria to measure the quality of generators or lattices. More...

enum	NormaType { BESTLAT , BESTBOUND , LAMINATED , ROGERS , MINKL1 , MINKL2 , NONE }
	Different types of normalizations that can be used for shortest-vector lengths. More...

enum	CalcType { PAL , NORMPAL , BAL , SEEKPAL }
	Indicates which type of calculation is considered for the $P_{\alpha}$ test. More...

enum	ReductionType { PAIR , LLL , BKZ , BB , PAIRBB , LLLBB , BKZBB }
	A list of all the possible lattice reductions implemented in `LatticeTester`. More...

enum	DecompTypeBB { CHOLESKY , TRIANGULAR }
	Two possible ways of obtaining a triangular matrix to compute the bounds in the BB algorithm. More...

enum	ProjConstructType { LLLPROJ , UPPERTRIPROJ }
	Two possible ways of computing the basis for a projection. More...

enum	MeritType { MERITM , MERITQ }
	Two different types of figures of merit. More...

Functions
template<typename IntMat , typename RealVec >
static long	LLLConstruction0 (IntMat &gen, const double delta=0.9, long r=0, long c=0, RealVec *sqlen=0)
	This static class offers methods (functions) to construct a basis from a set of generating vectors that are not necessarily independent, to construct a triangular basis, to construct the basis for a projection over a given subset of coordinates, and to obtain the $m$-dual of a given basis.

template<typename IntMat , typename Int , typename RealVec >
static void	LLLBasisConstruction (IntMat &gen, const Int &m, const double delta=0.9, long r=0, long c=0, RealVec *sqlen=0)
	Similar to `LLLConstruction0`, except that in case the set of generating vectors do not generate a full-dimensional lattice, it adds the vectors $m e_i$ to the generating set, so it always returns a square matrix.

template<typename IntMat , typename Int >
static void	lowerTriangularBasis (IntMat &gen, IntMat &basis, const Int &m, long r=0, long c=0)
	Takes a set of generating vectors in the matrix `gen` and iteratively transforms it into a lower triangular lattice basis into the matrix `basis`.

template<typename IntMat , typename Int >
static void	upperTriangularBasis (IntMat &gen, IntMat &basis, const Int &m, long r=0, long c=0)
	Same as `lowerTriangularBasis`, except that the returned basis is upper triangular.

template<typename IntMat , typename Int >
static void	mDualUpperTriangular (const IntMat &basis, IntMat &basisDual, const Int &m, long dim=0)
	Takes an upper triangular basis matrix `basis` and computes the m-dual basis `basisDual`.

template<typename IntMat , typename Int >
static void	mDualUpperTriangular96 (IntMat &basis, IntMat &basisDual, const Int &m, long dim=0)
	This function does essentially the same thing as `mDualUpperTriangular`, but the algorithm is slightly different.

template<typename IntMat , typename Int >
static void	mDualBasis (const IntMat &basis, IntMat &basisDual, const Int &m)
	This function assumes that `basis` contains a basis of the primal lattice scaled by the factor `m`, not necessarily triangular, and it returns in `basisDual` the m-dual basis.

template<typename IntMat >
static void	projectMatrix (const IntMat &in, IntMat &out, const Coordinates &proj, long r=0)
	This function overwrites the first `r` rows of matrix 'out' by a matrix formed by the first `r` rows of the c columns of matrix `in` that are specified by `proj`, where ‘c = size(proj)’ is the cardinality of the projection `proj`.

template<typename IntMat , typename Int , typename RealVec >
static void	projectionConstructionLLL (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, const double delta=0.9, long r=0, RealVec *sqlen=0)
	Constructs a basis for the projection `proj` of the lattice with basis `inBasis`, using `LLLBasisConstruction`, and returns it in `projBasis`.

template<typename IntMat , typename Int >
static void	projectionConstructionUpperTri (const IntMat &inBasis, IntMat &projBasis, IntMat &genTemp, const Coordinates &proj, const Int &m, long r=0)
	Same as `projectionConstructionLLL`, but the construction is made using `upperTriangularBasis`, so the returned basis is upper triangular.

template<typename IntMat , typename Int >
static void	projectionConstructionUpperTri (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, long r=0)

template<typename IntMat , typename Int >
static void	projectionConstruction (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, const ProjConstructType projType=LLLPROJ, const double delta=0.9)
	In this version, the construction method is passed as a parameter.

template<>
long	LLLConstruction0 (NTL::matrix< long > &gen, const double delta, long r, long c, NTL::vector< double > *sqlen)

template<>
long	LLLConstruction0 (NTL::matrix< NTL::ZZ > &gen, const double delta, long r, long c, NTL::vector< double > *sqlen)

template<>
long	LLLConstruction0 (NTL::matrix< NTL::ZZ > &gen, const double delta, long r, long c, NTL::vector< xdouble > *sqlen)

template<>
long	LLLConstruction0 (NTL::matrix< NTL::ZZ > &gen, const double delta, long r, long c, NTL::vector< quad_float > *sqlen)

template<>
long	LLLConstruction0 (NTL::matrix< NTL::ZZ > &gen, const double delta, long r, long c, NTL::vector< NTL::RR > *sqlen)

template<typename IntMat , typename Int , typename RealVec >
void	LLLBasisConstruction (IntMat &gen, const Int &m, double delta, long r, long c, RealVec *sqlen)
	Similar to `LLLConstruction0`, except that in case the set of generating vectors do not generate a full-dimensional lattice, it adds the vectors $m e_i$ to the generating set, so it always returns a square matrix.

template<typename IntMat , typename Int >
void	lowerTriangularBasis (IntMat &gen, IntMat &basis, const Int &m, long dim1, long dim2)
	Takes a set of generating vectors in the matrix `gen` and iteratively transforms it into a lower triangular lattice basis into the matrix `basis`.

template<typename IntMat , typename Int >
void	upperTriangularBasis (IntMat &gen, IntMat &basis, const Int &m, long dim1, long dim2)
	Same as `lowerTriangularBasis`, except that the returned basis is upper triangular.

template<typename IntMat , typename Int >
void	mDualUpperTriangular (const IntMat &A, IntMat &B, const Int &m, long dim)
	For `B` to be `m`-dual to `A`, we have to have that $AB^t = mI$.

template<typename IntMat , typename Int >
void	mDualUpperTriangular96 (IntMat &basis, IntMat &basisDual, const Int &m, long dim)
	This function does essentially the same thing as `mDualUpperTriangular`, but the algorithm is slightly different.

template<>
void	mDualUpperTriangular96 (NTL::matrix< NTL::ZZ > &basis, NTL::matrix< NTL::ZZ > &basisDual, const NTL::ZZ &m, long dim)

template<typename IntMat , typename Int >
void	mDualBasis (const IntMat &basis, IntMat &basisDual, const Int &m)
	This function assumes that `basis` contains a basis of the primal lattice scaled by the factor `m`, not necessarily triangular, and it returns in `basisDual` the m-dual basis.

template<>
void	mDualBasis (const NTL::matrix< NTL::ZZ > &basis, NTL::matrix< NTL::ZZ > &basisDual, const NTL::ZZ &m)

template<typename IntMat >
void	projectMatrix (const IntMat &in, IntMat &out, const Coordinates &proj, long r)
	This function overwrites the first `r` rows of matrix 'out' by a matrix formed by the first `r` rows of the c columns of matrix `in` that are specified by `proj`, where ‘c = size(proj)’ is the cardinality of the projection `proj`.

template<typename IntMat , typename Int , typename RealVec >
void	projectionConstructionLLL (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, const double delta, long r, RealVec *sqlen)
	Constructs a basis for the projection `proj` of the lattice with basis `inBasis`, using `LLLBasisConstruction`, and returns it in `projBasis`.

template<typename IntMat , typename Int >
void	projectionConstructionUpperTri (const IntMat &inBasis, IntMat &projBasis, IntMat &genTemp, const Coordinates &proj, const Int &m, long r)
	Same as `projectionConstructionLLL`, but the construction is made using `upperTriangularBasis`, so the returned basis is upper triangular.

template<typename IntMat , typename Int >
void	projectionConstructionUpperTri (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, long r)

template<typename IntMat , typename Int >
void	projectionConstruction (const IntMat &inBasis, IntMat &projBasis, const Coordinates &proj, const Int &m, const ProjConstructType projType, const double delta)
	In this version, the construction method is passed as a parameter.

std::string	toString (Chrono &timer)
	Returns the value of the duration from `timer`.

static std::string	toStringNorm (NormType norm)
	The following are functions for printing the `enum` constants in this module.

static std::string	toStringOutput (OutputType out)

static std::string	toStringProblem (ProblemType prob)

static std::string	toStringPrecision (PrecisionType precision)

static std::string	toStringPrime (PrimeType prim)

static std::string	toStringCriterion (CriterionType criter)

static std::string	toStringNorma (NormaType norma)

static std::string	toStringCalc (CalcType calc)

static std::string	toStringReduction (ReductionType reduct)

static std::string	toStringDecomp (DecompTypeBB decomp)

static std::string	toStringProjConstruct (ProjConstructType proj)

static std::string	toStringMeritType (MeritType merit)

double	sqrtReal (const double &a)

xdouble	sqrtReal (const xdouble &a)

quad_float	sqrtReal (const quad_float &a)

NTL::RR	sqrtReal (const NTL::RR &a)

std::int64_t	lFactorial (int64_t t)
	Calculates $t!$, the factorial of $t$.

double	Digamma (double x)
	Returns the value of the logarithmic derivative of the Gamma function $\psi(x) = \Gamma'(x) / \Gamma(x)$.

double	BernoulliPoly (int64_t n, double x)
	Evaluates the Bernoulli polynomial $B_n(x)$ of degree $n$ at $x$.

double	Harmonic (std::int64_t n)
	Computes the $n$-th harmonic number $H_n = \sum_{j=1}^n 1/j$.

double	Harmonic2 (std::int64_t n)
	Computes the sum.

double	FourierC1 (double x, std::int64_t n)
	Computes and returns the value of the series (see [5])

double	FourierE1 (double x, std::int64_t n)
	Computes and returns the value of the series.

void	negativeCholesky ()

template<typename IntMat , typename RealVec >
static void	redLLL (IntMat &basis, double delta=0.99999, long dim=0, RealVec *sqlen=0)
	This file provides only static functions to reduce a lattice basis in some ways (pairwise, LLL, BKZ [4], [9], [10]).

template<typename IntMat >
static void	redLLLExact (IntMat &basis, double delta=0.99999)
	This static function implements an exact algorithm from NTL to perform the original LLL reduction.

template<typename IntMat , typename RealVec >
static void	redBKZ (IntMat &basis, double delta=0.99999, int64_t blocksize=10, long prune=0, long dim=0, RealVec *sqlen=0)
	This calls the NTL implementation of the floating point version of the BKZ reduction algorithm presented in [10], with reduction factor `delta`, block size `blocksize`, pruning parameter ‘prune’; see [7].

template<typename IntMat , typename RealVec >
void	redLLL (IntMat &basis, double delta, long dim, RealVec *sqlen)
	This file provides only static functions to reduce a lattice basis in some ways (pairwise, LLL, BKZ [4], [9], [10]).

template<>
void	redLLL (NTL::matrix< int64_t > &basis, double delta, long dim, NTL::vector< double > *sqlen)

template<>
void	redLLL (NTL::matrix< NTL::ZZ > &basis, double delta, long dim, NTL::vector< double > *sqlen)

template<>
void	redLLL (NTL::matrix< NTL::ZZ > &basis, double delta, long dim, NTL::vector< xdouble > *sqlen)

template<>
void	redLLL (NTL::matrix< NTL::ZZ > &basis, double delta, long dim, NTL::vector< quad_float > *sqlen)

template<>
void	redLLL (NTL::matrix< NTL::ZZ > &basis, double delta, long dim, NTL::vector< NTL::RR > *sqlen)

template<typename IntMat >
void	redLLLExact (IntMat &basis, double delta)
	This static function implements an exact algorithm from NTL to perform the original LLL reduction.

template<>
void	redLLLExact (NTL::matrix< NTL::ZZ > &basis, double delta)

template<typename IntMat , typename RealVec >
void	redBKZ (IntMat &basis, double delta, long blocksize, long prune, long dim, RealVec *sqlen)

template<>
void	redBKZ (NTL::matrix< int64_t > &basis, double delta, long blocksize, long prune, long dim, NTL::vector< double > *sqlen)

template<>
void	redBKZ (NTL::matrix< NTL::ZZ > &basis, double delta, long blocksize, long prune, long dim, NTL::vector< double > *sqlen)

template<>
void	redBKZ (NTL::matrix< NTL::ZZ > &basis, double delta, long blocksize, long prune, long dim, NTL::vector< xdouble > *sqlen)

template<>
void	redBKZ (NTL::matrix< NTL::ZZ > &basis, double delta, long blocksize, long prune, long dim, NTL::vector< quad_float > *sqlen)

template<>
void	redBKZ (NTL::matrix< NTL::ZZ > &basis, double delta, long blocksize, long prune, long dim, NTL::vector< NTL::RR > *sqlen)

template<typename T >
void	swap9 (T &x, T &y)
	Takes references to two variables of a generic type and swaps their content.

template<typename Matr1 , typename Matr2 >
void	copyMatrixToMat (Matr1 &A, Matr2 &B)

template<typename IntMat >
void	printBase (IntMat bas_mat)

template<typename IntMat >
void	printBase2 (IntMat bas_mat)

template<typename IntMat >
void	copy (IntMat &b1, IntMat &b2)

template<typename IntMat >
void	copy (IntMat &b1, IntMat &b2, int64_t r, int64_t c)

int64_t	getWidth (clock_t time[], int64_t dim, std::string message, clock_t totals[], int64_t ind)

double	Harmonic (long n)

double	Harmonic2 (long n)

double	FourierC1 (double x, long n)

double	FourierE1 (double x, long n)

std::int64_t	RandInt (std::int64_t i, std::int64_t j)

static bool	check_next_chars (istream &is, const string &token)
	Helper function to check the next characters from an input stream.

static void	skip_any (istream &is, const string &characters)
	Helper function to skip all characters of a given class.

istream &	operator>> (std::istream &is, WeightsProjectionDependent &weights)

static std::ostream &	operator<< (std::ostream &os, const Coordinates &coords)
	Formats the coordinate set `coords` and outputs it to `os`.

static std::istream &	operator>> (std::istream &is, Coordinates &coords)
	Reads a formatted coordinate set from `is`.

std::ostream &	operator<< (std::ostream &os, const Weights &o)
	Identifies the type of weights, formats them and outputs them on `os`.

std::istream &	operator>> (std::istream &is, WeightsProjectionDependent &weights)
	Reads formatted projection-dependent weights into the object `weights`.

Random numbers
All the functions of this module use LFSR258 as an underlying source for pseudo-random numbers. A free (as in freedom) implementation of this generator can be found at http://simul.iro.umontreal.ca/ as well as the article presenting it. All the functions generating some sort of random number will advance an integer version of LFSR258 by one state and output a transformation of the state to give a double, an int64_t or bits.
double	RandU01 ()
	Returns a random number in $[0, 1)$.

int64_t	RandInt (int64_t i, int64_t j)
	Return a uniform pseudo-random integer in $[i, j]$.

std::uint64_t	RandBits (int64_t s)
	Returns the first s pseudo-random bits of the underlying RNG in the form of a s-bit integer.

void	SetSeed (std::uint64_t seed)
	Sets the seed of the generator.

Mathematical functions
These are complete reimplementation of certain mathematical functions, or wrappers for standard C/C++ functions.
double	mysqrt (double x)
	Returns $\sqrt{x}$ for $x\ge0$, and $-1$ for $x < 0$.

template<typename T >
double	Lg (const T &x)
	Returns the logarithm of $x$ in base 2.

double	Lg (std::int64_t x)
	Returns the logarithm of $x$ in base 2.

template<typename Scal >
Scal	abs (Scal x)
	Returns the absolute value of $x$.

template<typename T >
std::int64_t	sign (const T &x)
	Returns the sign of `x`.

template<typename Real >
Real	Round (Real x)
	Returns the value of x rounded to the NEAREST integer value.

std::int64_t	Factorial (int64_t t)
	Calculates $t!$, the factorial of $t$ and returns it as an std::int64_t.

Division and modular arithmetic
Remarks Richard: Pour certaines fonctions, les résultats sont mis dans les premiers arguments de la fonction pour être compatible avec NTL; pour d’autres, ils sont mis dans les derniers arguments pour être compatible avec notre ancienne version de LatMRG en Modula-2. Plutôt détestable. Je crois qu’il faudra un jour réarranger les arguments des fonctions pour qu’elles suivent toutes la même convention que NTL. This module offers function to perform division and find remainders in a standard way. These functions are usefull in the case where one wants to do divisions or find remainders of operations with negative operands. The reason is that NTL and primitive types do not use the same logic when doing calculations on negative numbers. Basically, NTL will always floor a division and C++ will always truncate a division (which effectively means the floor function is replaced by a roof function if the answer is a negative number). When calculating the remainder of x/y, both apply the same logic but get a different result because they do not do the same division. In both representations, we have that \[ y\cdot(x/y) + x%y = x. \] It turns out that, with negative values, NTL will return an integer with the same sign as y where C++ will return an integer of opposite sign (but both will return the same number modulo y).
template<typename Int >
void	Quotient (const Int &a, const Int &b, Int &q)
	Computes `a/b`, truncates the fractionnal part and puts the result in q.

template<typename Real >
void	Modulo (const Real &a, const Real &b, Real &r)
	Computes the remainder of a/b and stores its positive equivalent mod b in r.

template<typename Real >
void	Divide (Real &q, Real &r, const Real &a, const Real &b)
	Computes the quotient $q = a/b$ and remainder $r = a \bmod b$.

template<typename Real >
void	DivideRound (const Real &a, const Real &b, Real &q)
	Computes $a/b$, rounds the result to the nearest integer and returns the result in $q$.

std::int64_t	gcd (std::int64_t a, std::int64_t b)
	Returns the value of the greatest common divisor of $a$ and $b$ by using Stein's binary GCD algorithm.

template<typename Int >
void	Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &E, Int &F, Int &G)
	This method computes the greater common divisor of `A` and `B` with Euclid's algorithm.

template<typename Int >
void	Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &G)

template<typename IntMat >
void	TransposeMatrix (IntMat &mat, IntMat &mat2)
	Takes a set of generating vectors in the matrix `mat` and iteratively transforms it into an upper triangular lattice basis into the matrix `mat2`.

Vectors
These are utilities to manipulate vectors ranging from instantiation to scalar product.
template<typename Real >
void	CreateVect (Real *&A, int64_t d)
	Allocates memory to `A` as an array of `Real` of dimension `d` and initializes its elements to 0.

template<typename Vect >
void	CreateVect (Vect &A, int64_t d)
	Creates the vector `A` of dimensions `d+1` and initializes its elements to 0.

template<typename Real >
void	DeleteVect (Real *&A)
	Frees the memory used by the vector `A`.

template<typename Vect >
void	DeleteVect (Vect &A)
	Frees the memory used by the vector `A`, destroying all the elements it contains.

template<typename Real >
void	SetZero (Real *A, int64_t d)
	Sets the first `d` of `A` to 0.

template<typename Vect >
void	SetZero (Vect &A, int64_t d)
	Sets the first `d` components of `A` to 0.

template<typename Real >
void	SetValue (Real *A, int64_t d, const Real &x)
	Sets the first `d` components of `A` to 0.

template<typename Vect >
std::string	toString (const Vect &A, int64_t c, int64_t d, const char *sep=" ")
	Returns a string containing `A[c]` to `A[d-1]` formated as `[A[c]sep...sepA[d-1]]`.

template<typename Vect >
std::string	toString (const Vect &A, int64_t d)
	Returns a string containing the first `d` components of the vector `A` as a string.

template<typename Int , typename Vect1 , typename Vect2 , typename Scal >
void	ProdScal (const Vect1 &A, const Vect2 &B, int64_t n, Scal &D)
	Computes the scalar product of vectors `A` and `B` truncated to their `n` first components, then puts the result in `D`.

template<typename IntVec >
void	Invert (const IntVec &A, IntVec &B, int64_t n)
	Takes an input vector `A` of dimension `n+1` and fill the vector `B` with the values `[-A[n] -A[n-1] ... -A[1][1]`.

template<typename Vect , typename Scal >
void	CalcNorm (const Vect &V, int64_t n, Scal &S, NormType norm)
	Computes the `norm` norm of vector `V` trunctated to its `n` first components, and puts the result in `S`.

template<typename Vect >
void	CopyPartVec (Vect &toVec, const Vect &fromVec, int64_t c)
	Copies the first `c` components of vector `fromVec` into vector `toVec`.

template<typename Matr >
void	CopyPartMat (Matr &toMat, const Matr &fromMat, int64_t r, int64_t c)
	Copies the first `r` rows and `c` columns of matrix `fromMat` into matrix `toMat`.

template<typename Vect >
void	CopyVect (Vect &A, const Vect &B, int64_t n)
	Copies the first `n` components of vector `B` into vector `A`.

template<typename Vect1 , typename Vect2 , typename Scal >
void	ModifVect (Vect1 &A, const Vect2 &B, Scal x, int64_t n)
	Adds the first `n` components of vector `B` multiplied by `x` to first `n` components of vector `A`.

template<typename Vect >
void	ChangeSign (Vect &A, int64_t n)
	Changes the sign (multiplies by -1) the first `n` components of vector `A`.

std::int64_t	GCD2vect (std::vector< std::int64_t > V, int64_t k, int64_t n)
	Computes the greatest common divisor of `V[k],...,V[n-1]`.

Matrices
template<typename Real >
void	CreateMatr (Real **&A, int64_t d)
	Allocates memory to a square matrix `A` of dimensions $d \times d$ and initializes its elements to 0.

template<typename Real >
void	CreateMatr (Real **&A, int64_t line, int64_t col)
	Allocates memory for the matrix `A` of dimensions $\text{line} \times \text{col}$ and initializes its elements to 0.

template<typename IntMat >
void	CreateMatr (IntMat &A, int64_t d)
	Resizes the matrix `A` to a square matrix of dimensions `d*d` and re-initializes its elements to 0.

template<typename IntMat >
void	CreateMatr (IntMat &A, int64_t line, int64_t col)
	Resizes the matrix `A` to a matrix of dimensions $line \times col$ and re-initializes its elements to 0.

template<typename Real >
void	DeleteMatr (Real **&A, int64_t d)
	Frees the memory used by the $d \times d$ matrix `A`.

template<typename Real >
void	DeleteMatr (Real **&A, int64_t line, int64_t col)
	Frees the memory used by the matrix `A` of dimension $\text{line} \times \text{col}$.

template<typename IntMat >
void	DeleteMatr (IntMat &A)
	Calls the `clear()` method on `A`.

template<typename Matr >
void	CopyMatr (Matr &A, const Matr &B, int64_t n)
	Copies the $n \times n$ submatrix of the first lines and columns of `B` into matrix `A`.

template<typename Matr >
void	CopyMatr (Matr &A, const Matr &B, int64_t line, int64_t col)
	Copies the $\text{line} \times col$ submatrix of the first lines and columns of `B` into matrix `A`.

template<typename MatT >
std::string	toStr (const MatT &mat, int64_t d1, int64_t d2, int64_t prec=2)
	Returns a string that is a representation of `mat`.

template<typename Int >
void	ProductDiagonal (const NTL::matrix< Int > &A, long dim, Int &prod)
	Returns the product of the diagonal elements of the matrix `A`, which is assumed to be square `dim x dim`.

template<typename Int >
bool	CheckTriangular (const NTL::matrix< Int > &A, long dim, const Int m)
	Checks that the upper $\text{dim} \times \text{dim}$ submatrix of `A` is triangular modulo `m`.

template<typename Int >
bool	checkInverseModm (const NTL::matrix< Int > &A, const NTL::matrix< Int > &B, const Int m)
	Checks if A and B are m-dual to each other.

template<typename Matr , typename Int >
void	Triangularization (Matr &W, Matr &V, int64_t lin, int64_t col, const Int &m)
	Takes a set of generating vectors in the matrix `W` and iteratively transforms it into an upper triangular lattice basis into the matrix `V`.

template<typename Matr , typename Int >
void	calcDual (const Matr &A, Matr &B, int64_t d, const Int &m)
	Takes a basis `A` and computes an m-dual lattice basis B.

Debugging functions
void	MyExit (int64_t status, std::string msg)
	Special exit function.

Printing functions and operators
template<class K , class T , class C , class A >
std::ostream &	operator<< (std::ostream &out, const std::map< K, T, C, A > &x)
	Streaming operator for maps.

template<class T1 , class T2 >
std::ostream &	operator<< (std::ostream &out, const std::pair< T1, T2 > &x)
	Streaming operator for vectors.

template<class T , class A >
std::ostream &	operator<< (std::ostream &out, const std::vector< T, A > &x)
	Streaming operator for vectors.

template<class K , class C , class A >
std::ostream &	operator<< (std::ostream &out, const std::set< K, C, A > &x)
	Streaming operator for sets.

Variables
const double	MAX_LONG_DOUBLE = 9007199254740992.0
	Maximum integer that can be represented exactly as a `double`: $2^{53}$.

const std::int64_t	TWO_EXP []
	Table of powers of 2: `TWO_EXP[` $i$`]` $= 2^i$, $i=0, 1, …, 63$.

Detailed Description

Lattice namespace.

Typedef Documentation

◆ Weight

typedef double LatticeTester::Weight

A scalar weight type.

Enumeration Type Documentation

◆ CalcType

enum LatticeTester::CalcType

Indicates which type of calculation is considered for the $P_{\alpha}$ test.

Is this used anywhere? ************

PAL is for the $P_{\alpha}$ test.
BAL is for the bound on the $P_{\alpha}$ test.
NORMPAL is for the $P_{\alpha}$ test PAL, with the result normalized over the BAL bound.
SEEKPAL is for the $P_{\alpha}$ seek, which searches for good values of the multiplier.

Enumerator
PAL
NORMPAL
BAL
SEEKPAL

◆ CriterionType

enum LatticeTester::CriterionType

Merit criteria to measure the quality of generators or lattices.

TO DO: this list is not very clear. Maybe outdated. ****************

LENGTH: Only using the length of the shortest vector as a criterion. SPECTRAL: figure of merit $S_T$ based on the spectral test.
BEYER: figure of merit is the Beyer quotient $Q_T$.
PALPHA: figure of merit based on $P_{\alpha}$.
BOUND_JS: figure of merit based on the Joe-Sinescu bound [11].
???

Enumerator
LENGTH
SPECTRAL
BEYER
PALPHA
BOUND_JS

◆ DecompTypeBB

enum LatticeTester::DecompTypeBB

Two possible ways of obtaining a triangular matrix to compute the bounds in the BB algorithm.

CHOLESKY: use a lower-triangular matrix obtained as the Cholesky decomposition of the matrix of scalar products. TRIANGULAR: use a lower-triangular basis

Enumerator
CHOLESKY
TRIANGULAR

◆ MeritType

enum LatticeTester::MeritType

Two different types of figures of merit.

MERITM: based on shortest vector. MERITQ: based on Beyer quotient.

Enumerator
MERITM
MERITQ

◆ NormaType

enum LatticeTester::NormaType

Different types of normalizations that can be used for shortest-vector lengths.

Corresponds to different ways of approximating the Hermite constants gamma_t.

BESTLAT: the value used for $d_t^*$ corresponds to the best lattice.
BESTBOUND: the value used for $d_t^*$ corresponds to the best bound known to us.
LAMINATED: the value used for $d_t^*$ corresponds to the best laminated lattice.
ROGERS: the value for $d_t^*$ is obtained from Rogers’ bound on the density of sphere packing.
MINKL1: the value for $d_t^*$ is obtained from the theoretical bounds on the length of the shortest nonzero vector in the lattice using the ${\mathcal{L}}_1$ norm.
MINKL2: the value for $d_t^*$ is obtained from Minkowski’ theoretical bounds on the length of the shortest nonzero vector in the lattice using the ${\mathcal{L}}_2$ norm.
NONE: no normalization will be used.

Enumerator
BESTLAT
BESTBOUND
LAMINATED
ROGERS
MINKL1
MINKL2
NONE

◆ NormType

enum LatticeTester::NormType

The available norm types to measure the length of vectors.

For $X = (x_1,…,x_t)$:
SUPNORM corresponds to $\Vert X\Vert= \max(|x_1|,…,|x_t|)$.
L1NORM corresponds to $\Vert X\Vert= |x_1|+\cdots+|x_t|$.
L2NORM corresponds to $\Vert X\Vert= (x_1^2+\cdots+x_t^2)^{1/2}$.
ZAREMBANORM corresponds to $\Vert X\Vert= \max(1, |x_1|)\cdots\max(1, |x_t|)$.

Enumerator
SUPNORM
L1NORM
L2NORM
ZAREMBANORM

◆ OutputType

enum LatticeTester::OutputType

Different choices of output formats.

TERM: the results will appear only on the terminal screen.
RES: the results will be in plain text and sent to a .res file.
TEX: the results will be in a LaTeX file with extension .tex.
GEN: a list of retained generators will be sent to a file with extension .gen, in a specific format so this list can be read again for further analysis.

Enumerator
TERM
RES
TEX
GEN

◆ PrecisionType

enum LatticeTester::PrecisionType

This can be supersed by the Real type.

Types of precision that the NTL can use for real numbers: DOUBLE – double QUADRUPLE – quad_float (quasi quadruple precision) this is useful when roundoff errors can cause problems XDOUBLE – xdouble (extended exponent doubles) this is useful when numbers get too big RR – RR (arbitrary precision floating point). The choice DOUBLE is usually the fastest, but may be prone to roundoff errors and/or overflow. See https://github.com/u-u-h/NTL/blob/master/doc/LLL.txt.

Enumerator
DOUBLE
QUADRUPLE
XDOUBLE
RR

◆ PrimeType

enum LatticeTester::PrimeType

Indicates whether an integer is prime, probably prime, composite or its status is unknown (or we do not care).

Enumerator
PRIME
PROB_PRIME
COMPOSITE
UNKNOWN

◆ ProblemType

enum LatticeTester::ProblemType

Types of problems that LatticeTester can handle.

Not sure if we still need this. *******

Enumerator
BASIS
DUAL
REDUCTION
SHORTEST
MERIT

◆ ProjConstructType

enum LatticeTester::ProjConstructType

Two possible ways of computing the basis for a projection.

LLLPROJ: uses LLL reduction. UPPERTRIPROJ: use an upper-triangular basis construction.

Enumerator
LLLPROJ
UPPERTRIPROJ

◆ ReductionType

enum LatticeTester::ReductionType

A list of all the possible lattice reductions implemented in LatticeTester.

PAIR: Pairwise reductions only. LLL: LLL reduction only. BKZ: block Korkine-Zolotarev reduction only. BB: direct shortest vector search with BB (no pre-red.). PAIRBB: Pairwise reduction followed by BB. LLLBB: LLL followed by BB. BKZBB: BKZ followed by BB.

Enumerator
PAIR
LLL
BKZ
BB
PAIRBB
LLLBB
BKZBB

Function Documentation

◆ abs()

template<typename Scal >

Scal LatticeTester::abs ( Scal x )

inline

Returns the absolute value of $x$.

◆ BernoulliPoly()

double LatticeTester::BernoulliPoly	(	int64_t	n,
		double	x )

Evaluates the Bernoulli polynomial $B_n(x)$ of degree $n$ at $x$.

The first Bernoulli polynomials are:

\begin{align*} B_0(x) &= 1 \\ B_1(x) &= x - 1/2 \\ B_2(x) &= x^2-x+1/6 \\ B_3(x) &= x^3 - 3x^2/2 + x/2 \\ B_4(x) &= x^4-2x^3+x^2-1/30 \\ B_5(x) &= x^5 - 5x^4/2 + 5x^3/3 - x/6 \\ B_6(x) &= x^6-3x^5+5x^4/2-x^2/2+1/42 \\ B_7(x) &= x^7 - 7x^6/2 + 7x^5/2 - 7x^3/6 + x/6 \\ B_8(x) &= x^8-4x^7+14x^6/3 - 7x^4/3 +2x^2/3-1/30. \end{align*}

Only degrees $n \le 8$ are programmed for now.

◆ calcDual()

template<typename Matr , typename Int >

void LatticeTester::calcDual	(	const Matr &	A,
		Matr &	B,
		int64_t	d,
		const Int &	m )

Takes a basis A and computes an m-dual lattice basis B.

The matrix B is the m-dual basis of A. Takes an upper triangular basis A and computes an m-dual lattice basis to this matrix. For this algorithm to work, A has to be upper triangular and all the coefficients on the diagonal have to divide m.

For B to be 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$. 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}.\]

◆ CalcNorm()

template<typename Vect , typename Scal >

void LatticeTester::CalcNorm	(	const Vect &	V,
		int64_t	n,
		Scal &	S,
		NormType	norm )

inline

Computes the norm norm of vector V trunctated to its n first components, and puts the result in S.

Scal has to be a floating point type.

◆ ChangeSign()

template<typename Vect >

void LatticeTester::ChangeSign	(	Vect &	A,
		int64_t	n )

inline

Changes the sign (multiplies by -1) the first n components of vector A.

◆ check_next_chars()

static bool LatticeTester::check_next_chars	(	istream &	is,
		const string &	token )

static

Helper function to check the next characters from an input stream.

Returns true if the next characters in is are token. Upon a match, the characters are removed from is; otherwise, they are left in is.

◆ checkInverseModm()

template<typename Int >

bool LatticeTester::checkInverseModm	(	const NTL::matrix< Int > &	A,
		const NTL::matrix< Int > &	B,
		const Int	m )

Checks if A and B are m-dual to each other.

They must be square with the same dimensions. Returns true if AB = mI, false otherwise.

◆ CheckTriangular()

template<typename Int >

bool LatticeTester::CheckTriangular	(	const NTL::matrix< Int > &	A,
		long	dim,
		const Int	m )

Checks that the upper $\text{dim} \times \text{dim}$ submatrix of A is triangular modulo m.

This will return true if all the elements under the diagonal are equal to zero modulo m and false otherwise. If m is 0, this function simply verifies that the matrix is triangular.

◆ copy() [1/2]

template<typename IntMat >

void LatticeTester::copy	(	IntMat &	b1,
		IntMat &	b2 )

◆ copy() [2/2]

template<typename IntMat >

void LatticeTester::copy	(	IntMat &	b1,
		IntMat &	b2,
		int64_t	r,
		int64_t	c )

◆ CopyMatr() [1/2]

template<typename Matr >

void LatticeTester::CopyMatr	(	Matr &	A,
		const Matr &	B,
		int64_t	line,
		int64_t	col )

inline

Copies the $\text{line} \times col$ submatrix of the first lines and columns of B into matrix A.

This function does not check for sizes, so A and B both have to be at leat $line \times col$.

◆ CopyMatr() [2/2]

template<typename Matr >

void LatticeTester::CopyMatr	(	Matr &	A,
		const Matr &	B,
		int64_t	n )

inline

Copies the $n \times n$ submatrix of the first lines and columns of B into matrix A.

This function does not check for sizes, so A and B both have to be at leat $n \times n$.

◆ copyMatrixToMat()

template<typename Matr1 , typename Matr2 >

void LatticeTester::copyMatrixToMat	(	Matr1 &	A,
		Matr2 &	B )

◆ CopyPartMat()

template<typename Matr >

void LatticeTester::CopyPartMat	(	Matr &	toMat,
		const Matr &	fromMat,
		int64_t	r,
		int64_t	c )

inline

Copies the first r rows and c columns of matrix fromMat into matrix toMat.

◆ CopyPartVec()

template<typename Vect >

void LatticeTester::CopyPartVec	(	Vect &	toVec,
		const Vect &	fromVec,
		int64_t	c )

inline

Copies the first c components of vector fromVec into vector toVec.

◆ CopyVect()

template<typename Vect >

void LatticeTester::CopyVect	(	Vect &	A,
		const Vect &	B,
		int64_t	n )

inline

Copies the first n components of vector B into vector A.

◆ CreateMatr() [1/4]

template<typename IntMat >

void LatticeTester::CreateMatr	(	IntMat &	A,
		int64_t	d )

inline

Resizes the matrix A to a square matrix of dimensions d*d and re-initializes its elements to 0.

◆ CreateMatr() [2/4]

template<typename IntMat >

void LatticeTester::CreateMatr	(	IntMat &	A,
		int64_t	line,
		int64_t	col )

inline

Resizes the matrix A to a matrix of dimensions $line \times col$ and re-initializes its elements to 0.

◆ CreateMatr() [3/4]

template<typename Real >

void LatticeTester::CreateMatr	(	Real **&	A,
		int64_t	d )

inline

Allocates memory to a square matrix A of dimensions $d \times d$ and initializes its elements to 0.

◆ CreateMatr() [4/4]

template<typename Real >

void LatticeTester::CreateMatr	(	Real **&	A,
		int64_t	line,
		int64_t	col )

inline

Allocates memory for the matrix A of dimensions $\text{line} \times \text{col}$ and initializes its elements to 0.

◆ CreateVect() [1/2]

template<typename Real >

void LatticeTester::CreateVect	(	Real *&	A,
		int64_t	d )

inline

Allocates memory to A as an array of Real of dimension d and initializes its elements to 0.

Real has to be a numeric type.

◆ CreateVect() [2/2]

template<typename Vect >

void LatticeTester::CreateVect	(	Vect &	A,
		int64_t	d )

inline

Creates the vector A of dimensions d+1 and initializes its elements to 0.

The type Vect has to have a resize(integer_type) method that sets the size of the instance to the value of the argument.

◆ DeleteMatr() [1/3]

template<typename IntMat >

void LatticeTester::DeleteMatr ( IntMat & A )

inline

Calls the clear() method on A.

A has to have a clear() method that frees the memory allocated to it.

◆ DeleteMatr() [2/3]

template<typename Real >

void LatticeTester::DeleteMatr	(	Real **&	A,
		int64_t	d )

inline

Frees the memory used by the $d \times d$ matrix A.

This will not free all the memory allocated to A if A is of greater dimension and it can cause a memory leak.

◆ DeleteMatr() [3/3]

template<typename Real >

void LatticeTester::DeleteMatr	(	Real **&	A,
		int64_t	line,
		int64_t	col )

inline

Frees the memory used by the matrix A of dimension $\text{line} \times \text{col}$.

This will not free all the memory allocated to A if A is of greater dimension and it can cause a memory leak.

◆ DeleteVect() [1/2]

template<typename Real >

void LatticeTester::DeleteVect ( Real *& A )

inline

Frees the memory used by the vector A.

This calls delete[] on A so trying to access A after using this is unsafe.

◆ DeleteVect() [2/2]

template<typename Vect >

void LatticeTester::DeleteVect ( Vect & A )

inline

Frees the memory used by the vector A, destroying all the elements it contains.

Vect type has to have a clear() method that deallocates all the elements in the vector.

◆ Digamma()

double LatticeTester::Digamma ( double x )

Returns the value of the logarithmic derivative of the Gamma function $\psi(x) = \Gamma'(x) / \Gamma(x)$.

◆ Divide()

template<typename Real >

void LatticeTester::Divide	(	Real &	q,
		Real &	r,
		const Real &	a,
		const Real &	b )

inline

Computes the quotient $q = a/b$ and remainder $r = a \bmod b$.

Truncates $q$ to the nearest integer towards 0. One always has $a = qb + r$ and $|r| < |b|$. This works with std::int64_t, NTL::ZZ and real numbers.

$a$	$b$	$q$	$r$
$5$	3	1	$2$
$-5$	$3$	$-1$	$-2$
$5$	$-3$	$-1$	$2$
$-5$	$-3$	$1$	$-2$

◆ DivideRound()

template<typename Real >

void LatticeTester::DivideRound	(	const Real &	a,
		const Real &	b,
		Real &	q )

inline

Computes $a/b$, rounds the result to the nearest integer and returns the result in $q$.

This works with std::int64_t, NTL::ZZ and real numbers.

◆ Euclide() [1/2]

template<typename Int >

void LatticeTester::Euclide	(	const Int &	A,
		const Int &	B,
		Int &	C,
		Int &	D,
		Int &	E,
		Int &	F,
		Int &	G )

This method computes the greater common divisor of A and B with Euclid's algorithm.

This will store this gcd in G and also the linear combination that permits to get G from A and B. This function should work with std::int64_t and NTL::ZZ.

For $A$ and $B$ this will assign to $C$, $D$, $E$, $F$ and $G$ values such that:

\begin{align*} C a + D b & = G = \mbox{GCD } (a,b)\\ E a + F b & = 0. \end{align*}

◆ Euclide() [2/2]

template<typename Int >

void LatticeTester::Euclide	(	const Int &	A,
		const Int &	B,
		Int &	C,
		Int &	D,
		Int &	G )

◆ Factorial()

std::int64_t LatticeTester::Factorial ( int64_t t )

Calculates $t!$, the factorial of $t$ and returns it as an std::int64_t.

◆ FourierC1() [1/2]

double LatticeTester::FourierC1	(	double	x,
		long	n )

◆ FourierC1() [2/2]

double LatticeTester::FourierC1	(	double	x,
		std::int64_t	n )

Computes and returns the value of the series (see [5])

\[ S(x, n) = \sum_{j=1}^{n} \frac{\cos(2\pi j x)}{j}. \]

Restrictions: $n>0$ and $0 \le x \le 1$.

◆ FourierE1() [1/2]

double LatticeTester::FourierE1	(	double	x,
		long	n )

◆ FourierE1() [2/2]

double LatticeTester::FourierE1	(	double	x,
		std::int64_t	n )

Computes and returns the value of the series.

\[ G(x, n) = \sideset{}{'}\sum_{-n/2<h\le n/2}\; \frac{e^{2\pi i h x}}{|h|}, \]

where the symbol $\sum^\prime$ means that the term with $h=0$ is excluded from the sum, and assuming that the imaginary part of $G(x, n)$ vanishes. Restrictions: $n>0$ and $0 \le x \le 1$.

◆ gcd()

std::int64_t LatticeTester::gcd	(	std::int64_t	a,
		std::int64_t	b )

Returns the value of the greatest common divisor of $a$ and $b$ by using Stein's binary GCD algorithm.

◆ GCD2vect()

std::int64_t LatticeTester::GCD2vect	(	std::vector< std::int64_t >	V,
		int64_t	k,
		int64_t	n )

inline

Computes the greatest common divisor of V[k],...,V[n-1].

◆ getWidth()

int64_t LatticeTester::getWidth	(	clock_t	time[],
		int64_t	dim,
		std::string	message,
		clock_t	totals[],
		int64_t	ind )

inline

◆ Harmonic() [1/2]

double LatticeTester::Harmonic ( long n )

◆ Harmonic() [2/2]

double LatticeTester::Harmonic ( std::int64_t n )

Computes the $n$-th harmonic number $H_n = \sum_{j=1}^n 1/j$.

◆ Harmonic2() [1/2]

double LatticeTester::Harmonic2 ( long n )

◆ Harmonic2() [2/2]

double LatticeTester::Harmonic2 ( std::int64_t n )

Computes the sum.

\[ \sideset{}{'}\sum_{-n/2<j\le n/2}\; \frac 1{|j|}, \]

where the symbol $\sum^\prime$ means that the term with $j=0$ is excluded from the sum.

◆ Invert()

template<typename IntVec >

void LatticeTester::Invert	(	const IntVec &	A,
		IntVec &	B,
		int64_t	n )

inline

Takes an input vector A of dimension n+1 and fill the vector B with the values [-A[n] -A[n-1] ... -A[1][1].

B is assumed to be of dimension at least n+1.

◆ lFactorial()

std::int64_t LatticeTester::lFactorial ( int64_t t )

Calculates $t!$, the factorial of $t$.

Might throw if t is too large or if std::int64_t can't contain the factorial asked for.

◆ Lg() [1/2]

template<typename T >

double LatticeTester::Lg ( const T & x )

inline

Returns the logarithm of $x$ in base 2.

◆ Lg() [2/2]

double LatticeTester::Lg ( std::int64_t x )

inline

Returns the logarithm of $x$ in base 2.

◆ LLLBasisConstruction() [1/2]

template<typename IntMat , typename Int , typename RealVec >

static void LatticeTester::LLLBasisConstruction	(	IntMat &	gen,
		const Int &	m,
		const double	delta = 0.9,
		long	r = 0,
		long	c = 0,
		RealVec *	sqlen = 0 )

static

Similar to LLLConstruction0, except that in case the set of generating vectors do not generate a full-dimensional lattice, it adds the vectors $m e_i$ to the generating set, so it always returns a square matrix.

The matrix gen is not resized by this function, so it can remain larger than the lattice dimension.

◆ LLLBasisConstruction() [2/2]

template<typename IntMat , typename Int , typename RealVec >

void LatticeTester::LLLBasisConstruction	(	IntMat &	gen,
		const Int &	m,
		const double	delta = 0.9,
		long	r = 0,
		long	c = 0,
		RealVec *	sqlen = 0 )

Similar to LLLConstruction0, except that in case the set of generating vectors do not generate a full-dimensional lattice, it adds the vectors $m e_i$ to the generating set, so it always returns a square matrix.

The matrix gen is not resized by this function, so it can remain larger than the lattice dimension.

◆ LLLConstruction0() [1/6]

template<typename IntMat , typename RealVec >

static long LatticeTester::LLLConstruction0	(	IntMat &	gen,
		const double	delta = 0.9,
		long	r = 0,
		long	c = 0,
		RealVec *	sqlen = 0 )

static

This static class offers methods (functions) to construct a basis from a set of generating vectors that are not necessarily independent, to construct a triangular basis, to construct the basis for a projection over a given subset of coordinates, and to obtain the $m$-dual of a given basis.

The implementation relies on NTL and uses NTL matrices. When the basis turns out to have fewer rows than columns, some of the methods add implicitly the rescaled unit vectors to the set of generating vectors. In that case, the basis matrix is always square and all the vectors of the form $m \be_i$ belong to the lattice.

NTL already offers an efficient method to construct an LLL-reduced basis from a set of generating vectors. This is the most effective way of constructing a basis and it is encapsulated in the LLLConstruction0 method given below. This method does not assume that the rescaled unit vectors $m \be_i$ belong to the lattices and it does not even know about $m$. The method LLLBasisConstruction adds those vectors to the set of generating vectors, so it always returns a square basis.

We also offer an alternative methods that construct a triangular basis from a set of generating vectors. They always add the rescaled unit vectors implicitly to the set. The method lowerTriangularBasis constructs a lower-triangular basis, while upperTriangularBasis constructs an upper-triangular basis.

To compute the $m$-dual of a given basis, we have a general (but slow) method implemented in mDualBasis, and a much faster method in mDualUpperTriangular that works only when the basis is upper-triangular.

We also have functions to compute the basis of a projection of a given lattice over a specified set of coordinates. The function projectionConstructionLLL does this by using LLL to construct the basis of the projection, while projectionConstructionUpperTri constructs an upper-triangular basis for the projection. The function projectionConstruction takes the construction method as a parameter.

All functions take as input a IntMat object that contains either a basis or a set of generating vectors. By default, all rows and columns of this matrix object are used. But in most functions, the user can ask to use only a subset of these rows and columns, via the optional parameters r and c. This can permit one to use the same IntMat object for several numbers of dimensions, to avoid doing many object creations or resizing.

All functions in this class are static, so there is no reason to create any BasisConstruction object. We also avoid to create new objects (such as vectors and matrices) inside these functions. These functions can be called thousands or millions of times in a program, and we want the user to be able to re-use the same vectors and matrices over and over again instead of creating new ones.

Note that when one of these functions is used for an IntMat object that store the primal or $m$-dual basis inside an IntLattice object, only the primal or the $m$-dual basis is changed, and therefore the $m$-dual relationship will no longer hold after the call. The user must be aware of that. Most of the time, there is no need to reinstate this relationship, because for example if we want to compute a shortest nonzero vector is the $m$-dual lattice, then once we have an $m$-dual basis we no longer need a primal basis.

The programs BasisManipulationVerbose and BasisManipulation in the examples illustrate how to use these functions and make speed comparisons. This function takes a set of generating vectors of a lattice in matrix gen and finds a lattice basis by applying LLL reduction with the given value of delta, using the NTL implementation specified by prec. The basis is returned in the first rows of gen, in a number of rows equal to its rank. See the class EnumTypes and the documentation of LLL in NTL for the meaning and choices for prec. The default value of delta is not very close to 1 because the goal here is just to compute a basis. It can be taken much closer to 1 if we really prefer a highly-reduced basis. The optional parameters r and c indicate the numbers of rows and columns of the matrix gen that are actually used. When they are 0 (the default values), then these numbers are taken to be the dimensions of the matrix gen. When sqlen is not 0, the square lengths of the basis vectors are returned in this array, exactly as in the LLL_FPZZflex.h module. These optional parameters are allowed to take non-default values only when Int==ZZ and precision = DOUBLE. The function returns the dimension (number of rows) of the newly computed basis, which may differ from the number of rows of the gen object. The latter is never resized.

This function does not assume that all vectors $m e_i$ belong to the lattice, so it may return a basis matrix that has fewer rows than columns! To make sure that these vectors belong to the lattice, we can add them explicitly beforehand to the set of generating vectors, or call the next method.

◆ LLLConstruction0() [2/6]

template<>

long LatticeTester::LLLConstruction0	(	NTL::matrix< long > &	gen,
		const double	delta,
		long	r,
		long	c,
		NTL::vector< double > *	sqlen )

◆ LLLConstruction0() [3/6]

template<>

long LatticeTester::LLLConstruction0	(	NTL::matrix< NTL::ZZ > &	gen,
		const double	delta,
		long	r,
		long	c,
		NTL::vector< double > *	sqlen )

◆ LLLConstruction0() [4/6]

template<>

long LatticeTester::LLLConstruction0	(	NTL::matrix< NTL::ZZ > &	gen,
		const double	delta,
		long	r,
		long	c,
		NTL::vector< NTL::RR > *	sqlen )

◆ LLLConstruction0() [5/6]

template<>

long LatticeTester::LLLConstruction0	(	NTL::matrix< NTL::ZZ > &	gen,
		const double	delta,
		long	r,
		long	c,
		NTL::vector< quad_float > *	sqlen )

◆ LLLConstruction0() [6/6]

template<>

long LatticeTester::LLLConstruction0	(	NTL::matrix< NTL::ZZ > &	gen,
		const double	delta,
		long	r,
		long	c,
		NTL::vector< xdouble > *	sqlen )

◆ lowerTriangularBasis() [1/2]

template<typename IntMat , typename Int >

void LatticeTester::lowerTriangularBasis	(	IntMat &	gen,
		IntMat &	basis,
		const Int &	m,
		long	r = 0,
		long	c = 0 )

Takes a set of generating vectors in the matrix gen and iteratively transforms it into a lower triangular lattice basis into the matrix basis.

This lattice is assumed to contain all the vectors of the form $m e_j$, so these vectors are added implicitly to the generating set. Apart from that, all the entries of gen given as input are assumed to be reduced modulo the scaling factor m and all the computations are done modulo m. The matrix basis is assumed to be large enough to contain the new basis, whose dimension should be the number of columns taken from gen. After the execution, gen will contain irrelevant information (garbage) and basis will contain an upper triangular basis. The algorithm is explained in the lattice tester guide. Important: gen and basis must be different IntMat objects.

When r and/or c are strictly positive, they specify the numbers of rows and columns of gen that are actually used, as in LLLConstruction0. The matrix gen is never resized. The new basis should be c x c.

◆ lowerTriangularBasis() [2/2]

template<typename IntMat , typename Int >

static void LatticeTester::lowerTriangularBasis	(	IntMat &	gen,
		IntMat &	basis,
		const Int &	m,
		long	r = 0,
		long	c = 0 )

static

Takes a set of generating vectors in the matrix gen and iteratively transforms it into a lower triangular lattice basis into the matrix basis.

This lattice is assumed to contain all the vectors of the form $m e_j$, so these vectors are added implicitly to the generating set. Apart from that, all the entries of gen given as input are assumed to be reduced modulo the scaling factor m and all the computations are done modulo m. The matrix basis is assumed to be large enough to contain the new basis, whose dimension should be the number of columns taken from gen. After the execution, gen will contain irrelevant information (garbage) and basis will contain an upper triangular basis. The algorithm is explained in the lattice tester guide. Important: gen and basis must be different IntMat objects.

When r and/or c are strictly positive, they specify the numbers of rows and columns of gen that are actually used, as in LLLConstruction0. The matrix gen is never resized. The new basis should be c x c.

◆ mDualBasis() [1/3]

template<typename IntMat , typename Int >

static void LatticeTester::mDualBasis	(	const IntMat &	basis,
		IntMat &	basisDual,
		const Int &	m )

static

This function assumes that basis contains a basis of the primal lattice scaled by the factor m, not necessarily triangular, and it returns in basisDual the m-dual basis.

It uses matrix inversion and is rather slow. It is currently implemented only for Int = ZZ and it also assumes that the dimensions of the two IntMat objects is exactly the same as the dimensions of the lattices. The reason for this is that we use an NTL function that works only under these conditions.

◆ mDualBasis() [2/3]

template<typename IntMat , typename Int >

void LatticeTester::mDualBasis	(	const IntMat &	basis,
		IntMat &	basisDual,
		const Int &	m )

This function assumes that basis contains a basis of the primal lattice scaled by the factor m, not necessarily triangular, and it returns in basisDual the m-dual basis.

It uses matrix inversion and is rather slow. It is currently implemented only for Int = ZZ and it also assumes that the dimensions of the two IntMat objects is exactly the same as the dimensions of the lattices. The reason for this is that we use an NTL function that works only under these conditions.

◆ mDualBasis() [3/3]

template<>

void LatticeTester::mDualBasis	(	const NTL::matrix< NTL::ZZ > &	basis,
		NTL::matrix< NTL::ZZ > &	basisDual,
		const NTL::ZZ &	m )

◆ mDualUpperTriangular() [1/2]

template<typename IntMat , typename Int >

void LatticeTester::mDualUpperTriangular	(	const IntMat &	A,
		IntMat &	B,
		const Int &	m,
		long	dim )

For B to be m-dual to A, we have to have that $AB^t = mI$.

Takes an upper triangular basis matrix basis and computes the m-dual basis basisDual.

Since 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$. 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}.\]

◆ mDualUpperTriangular() [2/2]

template<typename IntMat , typename Int >

static void LatticeTester::mDualUpperTriangular	(	const IntMat &	A,
		IntMat &	B,
		const Int &	m,
		long	dim )

static

Takes an upper triangular basis matrix basis and computes the m-dual basis basisDual.

The method assumes that each coefficient on the diagonal of basis is nonzero and divides m. That is, the basis matrix must be square and invertible. The algorithm is described in the Lattice Tester guide [7]. Since the basis is upper triangular, its m-dual will be lower triangular. When dim > 0, it gives the number of rows and columns of the matrix basis that is actually used. Otherwise (by default) the method uses basis.numCols().

Takes an upper triangular basis matrix basis and computes the m-dual basis basisDual.

Since 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$. 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}.\]

◆ mDualUpperTriangular96() [1/3]

template<typename IntMat , typename Int >

void LatticeTester::mDualUpperTriangular96	(	IntMat &	basis,
		IntMat &	basisDual,
		const Int &	m,
		long	dim = 0 )

This function does essentially the same thing as mDualUpperTriangular, but the algorithm is slightly different.

It uses the method described in [3].

◆ mDualUpperTriangular96() [2/3]

template<typename IntMat , typename Int >

static void LatticeTester::mDualUpperTriangular96	(	IntMat &	basis,
		IntMat &	basisDual,
		const Int &	m,
		long	dim = 0 )

static

This function does essentially the same thing as mDualUpperTriangular, but the algorithm is slightly different.

It uses the method described in [3].

◆ mDualUpperTriangular96() [3/3]

template<>

void LatticeTester::mDualUpperTriangular96	(	NTL::matrix< NTL::ZZ > &	basis,
		NTL::matrix< NTL::ZZ > &	basisDual,
		const NTL::ZZ &	m,
		long	dim )

◆ ModifVect()

template<typename Vect1 , typename Vect2 , typename Scal >

void LatticeTester::ModifVect	(	Vect1 &	A,
		const Vect2 &	B,
		Scal	x,
		int64_t	n )

inline

Adds the first n components of vector B multiplied by x to first n components of vector A.

This will modify A. This does wierd type convertion and might not work well if different types are used.

◆ Modulo()

template<typename Real >

void LatticeTester::Modulo	(	const Real &	a,
		const Real &	b,
		Real &	r )

inline

Computes the remainder of a/b and stores its positive equivalent mod b in r.

This works with std::int64_t, NTL::ZZ and real numbers.

◆ MyExit()

void LatticeTester::MyExit	(	int64_t	status,
		std::string	msg )

Special exit function.

status is the status code to return to the system, msg is the message to print upon exit.

◆ mysqrt()

double LatticeTester::mysqrt ( double x )

inline

Returns $\sqrt{x}$ for $x\ge0$, and $-1$ for $x < 0$.

◆ negativeCholesky()

void LatticeTester::negativeCholesky ( )

◆ operator<<() [1/6]

template<class K , class T , class C , class A >

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::map< K, T, C, A > &	x )

Streaming operator for maps.

Formats a map as: { key1=>val1, ..., keyN=>valN }.

◆ operator<<() [2/6]

template<class T1 , class T2 >

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::pair< T1, T2 > &	x )

Streaming operator for vectors.

Formats a pair as: (first,second).

◆ operator<<() [3/6]

template<class K , class C , class A >

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::set< K, C, A > &	x )

Streaming operator for sets.

Formats a set as: { val1, ..., valN }.

◆ operator<<() [4/6]

template<class T , class A >

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::vector< T, A > &	x )

Streaming operator for vectors.

Formats a vector as: [ val1, ..., valN ].

◆ operator>>() [1/3]

istream & LatticeTester::operator>>	(	std::istream &	is,
		WeightsProjectionDependent &	weights )

template<typename IntMat >

void LatticeTester::printBase ( IntMat bas_mat )

◆ printBase2()

template<typename IntMat >

void LatticeTester::printBase2 ( IntMat bas_mat )

◆ ProdScal()

template<typename Int , typename Vect1 , typename Vect2 , typename Scal >

void LatticeTester::ProdScal	(	const Vect1 &	A,
		const Vect2 &	B,
		int64_t	n,
		Scal &	D )

inline

Computes the scalar product of vectors A and B truncated to their n first components, then puts the result in D.

There is a lot to consider when passing types to this function. The best is for Vect1 to be the same type as Vect2 and for Scal to be the same as Int, and that those types are the ones stored in Vect1 and Vect2.

WARNING: This uses so many types without check about them and also assumes all those types can be converted to each other without problem. This is used in many places to compute a floating point norm of vectors with integers values. Take care when using this function.

◆ ProductDiagonal()

template<typename Int >

void LatticeTester::ProductDiagonal	(	const NTL::matrix< Int > &	A,
		long	dim,
		Int &	prod )

Returns the product of the diagonal elements of the matrix A, which is assumed to be square dim x dim.

◆ projectionConstruction() [1/2]

template<typename IntMat , typename Int >

void LatticeTester::projectionConstruction	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		const ProjConstructType	projType = LLLPROJ,
		const double	delta = 0.9 )

In this version, the construction method is passed as a parameter.

The default is LLL. In the triangular case, a temporary matrix is created internally.

◆ projectionConstruction() [2/2]

template<typename IntMat , typename Int >

static void LatticeTester::projectionConstruction	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		const ProjConstructType	projType = LLLPROJ,
		const double	delta = 0.9 )

static

In this version, the construction method is passed as a parameter.

The default is LLL. In the triangular case, a temporary matrix is created internally.

◆ projectionConstructionLLL() [1/2]

template<typename IntMat , typename Int , typename RealVec >

void LatticeTester::projectionConstructionLLL	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		const double	delta = 0.9,
		long	r = 0,
		RealVec *	sqlen = 0 )

Constructs a basis for the projection proj of the lattice with basis inBasis, using LLLBasisConstruction, and returns it in projBasis.

This returned basis is not triangular in general. Its dimension will be the number of coordinates in proj. The matrix projBasis must have enough columns to hold it and at least as many rows as the number of rows that we use from inBasis. When r > 0, only the first r rows of the matrix inBasis are used, otherwise we use all rows of that matrix. This r should normally be the true dimension dim of that basis, which is often smaller than the size maxDim of the IntMat object that contains the basis. The square Euclidean lengths of the basis vectors are returned in the array sqlen when the latter is given.

◆ projectionConstructionLLL() [2/2]

template<typename IntMat , typename Int , typename RealVec >

static void LatticeTester::projectionConstructionLLL	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		const double	delta = 0.9,
		long	r = 0,
		RealVec *	sqlen = 0 )

static

Constructs a basis for the projection proj of the lattice with basis inBasis, using LLLBasisConstruction, and returns it in projBasis.

This returned basis is not triangular in general. Its dimension will be the number of coordinates in proj. The matrix projBasis must have enough columns to hold it and at least as many rows as the number of rows that we use from inBasis. When r > 0, only the first r rows of the matrix inBasis are used, otherwise we use all rows of that matrix. This r should normally be the true dimension dim of that basis, which is often smaller than the size maxDim of the IntMat object that contains the basis. The square Euclidean lengths of the basis vectors are returned in the array sqlen when the latter is given.

◆ projectionConstructionUpperTri() [1/4]

template<typename IntMat , typename Int >

void LatticeTester::projectionConstructionUpperTri	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		long	r )

◆ projectionConstructionUpperTri() [2/4]

template<typename IntMat , typename Int >

static void LatticeTester::projectionConstructionUpperTri	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		const Coordinates &	proj,
		const Int &	m,
		long	r = 0 )

static

◆ projectionConstructionUpperTri() [3/4]

template<typename IntMat , typename Int >

void LatticeTester::projectionConstructionUpperTri	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		IntMat &	genTemp,
		const Coordinates &	proj,
		const Int &	m,
		long	r = 0 )

Same as projectionConstructionLLL, but the construction is made using upperTriangularBasis, so the returned basis is upper triangular.

When r > 0, only the first r rows of the matrix inBasis are actually used, otherwise we use all rows of that matrix. In the first version, we pass a matrix genTemp that will be used to store the generating vectors of the projection before making the triangularization. The two matrices projBasis and genTemp must have enough columns to hold the projection and at least as many rows as the number of rows that we use from inBasis. We pass genTemp as a parameter to avoid the internal creation of a new matrix each time, in case we call this method several times. Its contents will be modified. In the second version, this matrix is not passed and a temporary one is created internally, which may add a bit of overhead.

◆ projectionConstructionUpperTri() [4/4]

template<typename IntMat , typename Int >

static void LatticeTester::projectionConstructionUpperTri	(	const IntMat &	inBasis,
		IntMat &	projBasis,
		IntMat &	genTemp,
		const Coordinates &	proj,
		const Int &	m,
		long	r = 0 )

static

Same as projectionConstructionLLL, but the construction is made using upperTriangularBasis, so the returned basis is upper triangular.

When r > 0, only the first r rows of the matrix inBasis are actually used, otherwise we use all rows of that matrix. In the first version, we pass a matrix genTemp that will be used to store the generating vectors of the projection before making the triangularization. The two matrices projBasis and genTemp must have enough columns to hold the projection and at least as many rows as the number of rows that we use from inBasis. We pass genTemp as a parameter to avoid the internal creation of a new matrix each time, in case we call this method several times. Its contents will be modified. In the second version, this matrix is not passed and a temporary one is created internally, which may add a bit of overhead.

◆ projectMatrix() [1/2]

template<typename IntMat >

void LatticeTester::projectMatrix	(	const IntMat &	in,
		IntMat &	out,
		const Coordinates &	proj,
		long	r = 0 )

This function overwrites the first r rows of matrix 'out' by a matrix formed by the first r rows of the c columns of matrix in that are specified by proj, where ‘c = size(proj)’ is the cardinality of the projection proj.

Only the first c columns of the first r rows are overwritten; the other entries are left unchanged. If r = 0, then all the rows of matrix in are taken. When in is a basis, r will usually be the dimension of that basis and c will be smaller. The dimensions of the matrices in and out are always left unchanged. The dimensions of out are assumed to be large enough. After the call, the matrix out will then contain a set of generating vectors for the projection proj. The matrices in and out must be different IntMat objects, otherwise the program halts with an error message.

◆ projectMatrix() [2/2]

template<typename IntMat >

static void LatticeTester::projectMatrix	(	const IntMat &	in,
		IntMat &	out,
		const Coordinates &	proj,
		long	r = 0 )

static

This function overwrites the first r rows of matrix 'out' by a matrix formed by the first r rows of the c columns of matrix in that are specified by proj, where ‘c = size(proj)’ is the cardinality of the projection proj.

Only the first c columns of the first r rows are overwritten; the other entries are left unchanged. If r = 0, then all the rows of matrix in are taken. When in is a basis, r will usually be the dimension of that basis and c will be smaller. The dimensions of the matrices in and out are always left unchanged. The dimensions of out are assumed to be large enough. After the call, the matrix out will then contain a set of generating vectors for the projection proj. The matrices in and out must be different IntMat objects, otherwise the program halts with an error message.

◆ Quotient()

template<typename Int >

void LatticeTester::Quotient	(	const Int &	a,
		const Int &	b,
		Int &	q )

inline

Computes a/b, truncates the fractionnal part and puts the result in q.

This function is overloaded to work as specified on NTL::ZZ integers. Example:

$a$	$b$	$q$
$5$	3	1
$-5$	$3$	$-1$
$5$	$-3$	$-1$
$-5$	$-3$	$1$

◆ RandBits()

std::uint64_t LatticeTester::RandBits ( int64_t s )

Returns the first s pseudo-random bits of the underlying RNG in the form of a s-bit integer.

It is imperative that $1 \leq s \leq 64$ because the RNG is 64 bits wide.

◆ RandInt() [1/2]

int64_t LatticeTester::RandInt	(	int64_t	i,
		int64_t	j )

Return a uniform pseudo-random integer in $[i, j]$.

Note that the numbers $i$ and $j$ are part of the possible output. It is important that $i < j$ because the underlying arithmetic uses unsigned integers to store j-i+1 and that will be undefined behavior.

◆ RandInt() [2/2]

std::int64_t LatticeTester::RandInt	(	std::int64_t	i,
		std::int64_t	j )

◆ RandU01()

double LatticeTester::RandU01 ( )

Returns a random number in $[0, 1)$.

The number will have 53 pseudo-random bits.

◆ redBKZ() [1/7]

template<typename IntMat , typename RealVec >

void LatticeTester::redBKZ	(	IntMat &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		RealVec *	sqlen )

◆ redBKZ() [2/7]

template<typename IntMat , typename RealVec >

static void LatticeTester::redBKZ	(	IntMat &	basis,
		double	delta = 0.99999,
		int64_t	blocksize = 10,
		long	prune = 0,
		long	dim = 0,
		RealVec *	sqlen = 0 )

static

This calls the NTL implementation of the floating point version of the BKZ reduction algorithm presented in [10], with reduction factor delta, block size blocksize, pruning parameter ‘prune’; see [7].

The other paraameters have the same meaning as in redLLLNTL. The parameter blocksize gives the size of the blocks in the BKZ reduction. Roughly, larger blocks means a stronger condition. A blocksize of 2 is equivalent to LLL reduction.

◆ redBKZ() [3/7]

template<>

void LatticeTester::redBKZ	(	NTL::matrix< int64_t > &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		NTL::vector< double > *	sqlen )

◆ redBKZ() [4/7]

template<>

void LatticeTester::redBKZ	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		NTL::vector< double > *	sqlen )

◆ redBKZ() [5/7]

template<>

void LatticeTester::redBKZ	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		NTL::vector< NTL::RR > *	sqlen )

◆ redBKZ() [6/7]

template<>

void LatticeTester::redBKZ	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		NTL::vector< quad_float > *	sqlen )

◆ redBKZ() [7/7]

template<>

void LatticeTester::redBKZ	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	blocksize,
		long	prune,
		long	dim,
		NTL::vector< xdouble > *	sqlen )

◆ redLLL() [1/7]

template<typename IntMat , typename RealVec >

void LatticeTester::redLLL	(	IntMat &	basis,
		double	delta = 0.99999,
		long	dim = 0,
		RealVec *	sqlen = 0 )

This file provides only static functions to reduce a lattice basis in some ways (pairwise, LLL, BKZ [4], [9], [10]).

The LLL and BKZ ones are wrappers to slightly modified versions of the NTL functions described at https://libntl.org/doc/LLL.cpp.html . These functions do not require the creation of an object like in ReducerBB. They take an IntMat object that contains a basis and return the reduced basis in the same object. In our versions, the basis can occupy only part of the IntMat object so we can use the same object for several bases of various sizes, the basis entries can be of either ZZ or int64_t type, the shortest basis vector is always placed in the first row, and the squared vector lengths are also returned in a vector. The norm to measure the vector lengths is always taken as the Euclidean one. The computations can be done either in double or in RR for the real numbers.

All these functions take as input (and return as output) an IntMat object whose first dim rows and columns (a square matrix) are assumed to form be a set of independent vectors that form a basis for the lattice. The same IntMat object can then be used for several lattices of different sizes. This function uses the NTL implementation of the LLL reduction algorithm with factor delta, presented in [10] (see also [7]). The reduction is applied to the first dim basis vectors and coordinates when dim > 0, and to the entire basis (all vectors) when dim=0. In the former case, the transformations are not applied to all the columns, so we will no longer have a consistent basis for the original lattice if it had more than dim dimensions. To recover a basis for the full lattice in this case, we may save it before calling this function, or rebuild it.

This function always uses the Euclidean norm. The factor delta must be between 1/2 and 1. The closer it is to 1, the more the basis is reduced, in the sense that the LLL algorithm will enforce tighter conditions on the basis. The returned basis always has its shortest vector in first place. The vector pointed by sqlen (if given) will contain the square lengths of the basis vectors. To recover these values in a Vec<double> v one can pass &v to the function. The parameter precision specifies the precision of the floating point numbers that the algorithm will use. EnumTypes.h provides a list of the possible values, and their description is done in the module LLL of NTL.

◆ redLLL() [2/7]

template<typename IntMat , typename RealVec >

static void LatticeTester::redLLL	(	IntMat &	basis,
		double	delta = 0.99999,
		long	dim = 0,
		RealVec *	sqlen = 0 )

static

This file provides only static functions to reduce a lattice basis in some ways (pairwise, LLL, BKZ [4], [9], [10]).

The LLL and BKZ ones are wrappers to slightly modified versions of the NTL functions described at https://libntl.org/doc/LLL.cpp.html . These functions do not require the creation of an object like in ReducerBB. They take an IntMat object that contains a basis and return the reduced basis in the same object. In our versions, the basis can occupy only part of the IntMat object so we can use the same object for several bases of various sizes, the basis entries can be of either ZZ or int64_t type, the shortest basis vector is always placed in the first row, and the squared vector lengths are also returned in a vector. The norm to measure the vector lengths is always taken as the Euclidean one. The computations can be done either in double or in RR for the real numbers.

All these functions take as input (and return as output) an IntMat object whose first dim rows and columns (a square matrix) are assumed to form be a set of independent vectors that form a basis for the lattice. The same IntMat object can then be used for several lattices of different sizes. This function uses the NTL implementation of the LLL reduction algorithm with factor delta, presented in [10] (see also [7]). The reduction is applied to the first dim basis vectors and coordinates when dim > 0, and to the entire basis (all vectors) when dim=0. In the former case, the transformations are not applied to all the columns, so we will no longer have a consistent basis for the original lattice if it had more than dim dimensions. To recover a basis for the full lattice in this case, we may save it before calling this function, or rebuild it.

This function always uses the Euclidean norm. The factor delta must be between 1/2 and 1. The closer it is to 1, the more the basis is reduced, in the sense that the LLL algorithm will enforce tighter conditions on the basis. The returned basis always has its shortest vector in first place. The vector pointed by sqlen (if given) will contain the square lengths of the basis vectors. To recover these values in a Vec<double> v one can pass &v to the function. The parameter precision specifies the precision of the floating point numbers that the algorithm will use. EnumTypes.h provides a list of the possible values, and their description is done in the module LLL of NTL.

◆ redLLL() [3/7]

template<>

void LatticeTester::redLLL	(	NTL::matrix< int64_t > &	basis,
		double	delta,
		long	dim,
		NTL::vector< double > *	sqlen )

◆ redLLL() [4/7]

template<>

void LatticeTester::redLLL	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	dim,
		NTL::vector< double > *	sqlen )

◆ redLLL() [5/7]

template<>

void LatticeTester::redLLL	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	dim,
		NTL::vector< NTL::RR > *	sqlen )

◆ redLLL() [6/7]

template<>

void LatticeTester::redLLL	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	dim,
		NTL::vector< quad_float > *	sqlen )

◆ redLLL() [7/7]

template<>

void LatticeTester::redLLL	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta,
		long	dim,
		NTL::vector< xdouble > *	sqlen )

◆ redLLLExact() [1/3]

template<typename IntMat >

void LatticeTester::redLLLExact	(	IntMat &	basis,
		double	delta = 0.99999 )

This static function implements an exact algorithm from NTL to perform the original LLL reduction.

This is slower than redLLLNTL, but more accurate. It does not take the dim and sqlen parameters (for now).

◆ redLLLExact() [2/3]

template<typename IntMat >

static void LatticeTester::redLLLExact	(	IntMat &	basis,
		double	delta = 0.99999 )

static

This static function implements an exact algorithm from NTL to perform the original LLL reduction.

This is slower than redLLLNTL, but more accurate. It does not take the dim and sqlen parameters (for now).

◆ redLLLExact() [3/3]

template<>

void LatticeTester::redLLLExact	(	NTL::matrix< NTL::ZZ > &	basis,
		double	delta )

◆ Round()

template<typename Real >

Real LatticeTester::Round ( Real x )

inline

Returns the value of x rounded to the NEAREST integer value.

(This does not truncate the integer value as is usual in computer arithmetic.)

◆ SetSeed()

void LatticeTester::SetSeed ( std::uint64_t seed )

Sets the seed of the generator.

Because of the constraints on the state, seed has to be $ > 2$. If this is never called, a default seed will be used.

◆ SetValue()

template<typename Real >

void LatticeTester::SetValue	(	Real *	A,
		int64_t	d,
		const Real &	x )

inline

Sets the first d components of A to 0.

Sets the first d components of A to the value x.

◆ SetZero() [1/2]

template<typename Real >

void LatticeTester::SetZero	(	Real *	A,
		int64_t	d )

inline

Sets the first d of A to 0.

◆ SetZero() [2/2]

template<typename Vect >

void LatticeTester::SetZero	(	Vect &	A,
		int64_t	d )

inline

Sets the first d components of A to 0.

◆ sign()

template<typename T >

std::int64_t LatticeTester::sign ( const T & x )

inline

Returns the sign of x.

The sign is 1 if x>0, 0 if x==0 and -1 if x<0.

◆ skip_any()

static void LatticeTester::skip_any	(	istream &	is,
		const string &	characters )

static

Helper function to skip all characters of a given class.

◆ sqrtReal() [1/4]

double LatticeTester::sqrtReal ( const double & a )

inline

◆ sqrtReal() [2/4]

NTL::RR LatticeTester::sqrtReal ( const NTL::RR & a )

inline

◆ sqrtReal() [3/4]

quad_float LatticeTester::sqrtReal ( const quad_float & a )

inline

◆ sqrtReal() [4/4]

xdouble LatticeTester::sqrtReal ( const xdouble & a )

inline

◆ swap9()

template<typename T >

void LatticeTester::swap9	(	T &	x,
		T &	y )

inline

Takes references to two variables of a generic type and swaps their content.

This uses the assignment operator, so it might not always work well if this operator's implementation is not thorough.

◆ toStr()

template<typename MatT >

std::string LatticeTester::toStr	(	const MatT &	mat,
		int64_t	d1,
		int64_t	d2,
		int64_t	prec = 2 )

Returns a string that is a representation of mat.

This string represents the $d1 \times d2$ submatrix of the first lines and columns of mat.

◆ toString() [1/3]

std::string LatticeTester::toString ( Chrono & timer )

Returns the value of the duration from timer.

◆ toString() [2/3]

template<typename Vect >

std::string LatticeTester::toString	(	const Vect &	A,
		int64_t	c,
		int64_t	d,
		const char *	sep = " " )

Returns a string containing A[c] to A[d-1] formated as [A[c]sep...sepA[d-1]].

In this string, components are separated by string sep. By default, sep is just a whitespace character.

◆ toString() [3/3]

template<typename Vect >

std::string LatticeTester::toString	(	const Vect &	A,
		int64_t	d )

Returns a string containing the first d components of the vector A as a string.

Calls toString(const Vect&, int, int, const char*).

◆ toStringCalc()

static std::string LatticeTester::toStringCalc ( CalcType calc )

static

◆ toStringCriterion()

static std::string LatticeTester::toStringCriterion ( CriterionType criter )

static

◆ toStringDecomp()

static std::string LatticeTester::toStringDecomp ( DecompTypeBB decomp )

static

◆ toStringMeritType()

static std::string LatticeTester::toStringMeritType ( MeritType merit )

static

◆ toStringNorm()

static std::string LatticeTester::toStringNorm ( NormType norm )

static

The following are functions for printing the enum constants in this module.

Each function returns the value of the enum variable given as input as a string.

◆ toStringNorma()

static std::string LatticeTester::toStringNorma ( NormaType norma )

static

◆ toStringOutput()

static std::string LatticeTester::toStringOutput ( OutputType out )

static

◆ toStringPrecision()

static std::string LatticeTester::toStringPrecision ( PrecisionType precision )

static

◆ toStringPrime()

static std::string LatticeTester::toStringPrime ( PrimeType prim )

static

◆ toStringProblem()

static std::string LatticeTester::toStringProblem ( ProblemType prob )

static

◆ toStringProjConstruct()

static std::string LatticeTester::toStringProjConstruct ( ProjConstructType proj )

static

◆ toStringReduction()

static std::string LatticeTester::toStringReduction ( ReductionType reduct )

static

◆ TransposeMatrix()

template<typename IntMat >

void LatticeTester::TransposeMatrix	(	IntMat &	mat,
		IntMat &	mat2 )

Takes a set of generating vectors in the matrix mat and iteratively transforms it into an upper triangular lattice basis into the matrix mat2.

mat and mat2 have to have the same number of rows and the same number of columns. All the computations will be done modulo mod, which means that you must know the rescaling factor for the vector system to call this function. After the execution, mat will be a matrix containing irrelevant information and mat2 will contain an upper triangular basis.

For more details please look at [latTesterGide]. This algorithm basically implements what is written in this guide. The matrix mat contains the set of vectors that is used and modified at each step to get a new vector from the basis. Lower triangularization

◆ Triangularization()

template<typename Matr , typename Int >

void LatticeTester::Triangularization	(	Matr &	W,
		Matr &	V,
		int64_t	lin,
		int64_t	col,
		const Int &	m )

Takes a set of generating vectors in the matrix W and iteratively transforms it into an upper triangular lattice basis into the matrix V.

W and V have to have more rows than lin and more columns than col since this algorithm will only operate on the upper lin*col matrix of W. All the computations will be done modulo m, which means that you must know the rescaling factor for the vector system to call this function. After the execution, W will be a matrix containing irrelevant information and V will contain an upper triangular basis.

For more details please look at [3]. This algorithm basically implements what is written at the end of the article, that is the matrix W contains the set of vectors that is used and modified at each step to get a new vector from the basis.

◆ upperTriangularBasis() [1/2]

template<typename IntMat , typename Int >

void LatticeTester::upperTriangularBasis	(	IntMat &	gen,
		IntMat &	basis,
		const Int &	m,
		long	dim1,
		long	dim2 )

Same as lowerTriangularBasis, except that the returned basis is upper triangular.

◆ upperTriangularBasis() [2/2]

template<typename IntMat , typename Int >

static void LatticeTester::upperTriangularBasis	(	IntMat &	gen,
		IntMat &	basis,
		const Int &	m,
		long	r = 0,
		long	c = 0 )

static

Same as lowerTriangularBasis, except that the returned basis is upper triangular.

Variable Documentation

◆ MAX_LONG_DOUBLE

const double LatticeTester::MAX_LONG_DOUBLE = 9007199254740992.0

Maximum integer that can be represented exactly as a double: $2^{53}$.

◆ TWO_EXP

const std::int64_t LatticeTester::TWO_EXP

Initial value:

= {
    1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
    33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
    4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
    274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104,
    8796093022208, 17592186044416, 35184372088832, 70368744177664,
    140737488355328, 281474976710656, 562949953421312, 1125899906842624,
    2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984,
    36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744,
    576460752303423488, 1152921504606846976, 2305843009213693952,
    (std::int64_t)4611686018427387904U, (std::int64_t)9223372036854775808U }

Table of powers of 2: TWO_EXP[ $i$] $= 2^i$, $i=0, 1, …, 63$.

\(a\)	\(b\)	\(q\)	\(r\)
\(5\)	3	1	\(2\)
\(-5\)	\(3\)	\(-1\)	\(-2\)
\(5\)	\(-3\)	\(-1\)	\(2\)
\(-5\)	\(-3\)	\(1\)	\(-2\)

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ Weight

Enumeration Type Documentation

◆ CalcType

◆ CriterionType

◆ DecompTypeBB

◆ MeritType

◆ NormaType

◆ NormType

◆ OutputType

◆ PrecisionType

◆ PrimeType

◆ ProblemType

◆ ProjConstructType

◆ ReductionType

Function Documentation

◆ abs()

◆ BernoulliPoly()

◆ calcDual()

◆ CalcNorm()

◆ ChangeSign()

◆ check_next_chars()

◆ checkInverseModm()

◆ CheckTriangular()

◆ copy() [1/2]

◆ copy() [2/2]

◆ CopyMatr() [1/2]

◆ CopyMatr() [2/2]

◆ copyMatrixToMat()

◆ CopyPartMat()

◆ CopyPartVec()

◆ CopyVect()

◆ CreateMatr() [1/4]

◆ CreateMatr() [2/4]

◆ CreateMatr() [3/4]

◆ CreateMatr() [4/4]

◆ CreateVect() [1/2]

◆ CreateVect() [2/2]

◆ DeleteMatr() [1/3]

◆ DeleteMatr() [2/3]

◆ DeleteMatr() [3/3]

◆ DeleteVect() [1/2]

◆ DeleteVect() [2/2]

◆ Digamma()

◆ Divide()

◆ DivideRound()

◆ Euclide() [1/2]

◆ Euclide() [2/2]

◆ Factorial()

◆ FourierC1() [1/2]

◆ FourierC1() [2/2]

◆ FourierE1() [1/2]

◆ FourierE1() [2/2]

◆ gcd()

◆ GCD2vect()

◆ getWidth()

◆ Harmonic() [1/2]

◆ Harmonic() [2/2]

◆ Harmonic2() [1/2]

◆ Harmonic2() [2/2]

◆ Invert()

◆ lFactorial()

◆ Lg() [1/2]

◆ Lg() [2/2]

◆ LLLBasisConstruction() [1/2]

◆ LLLBasisConstruction() [2/2]

◆ LLLConstruction0() [1/6]

◆ LLLConstruction0() [2/6]

◆ LLLConstruction0() [3/6]

◆ LLLConstruction0() [4/6]

◆ LLLConstruction0() [5/6]

◆ LLLConstruction0() [6/6]

◆ lowerTriangularBasis() [1/2]