Lattice namespace. More...

Namespaces
	CoordinateSets
	A classes containing multiple sets of coordinates.

Classes
class	Coordinates
	This is basically a `std::set<std::size_t>`. More...

class	IntFactor
	The objects of this class are the "prime" factors in the decomposition of a positive integer. More...

class	IntLattice
	This class is a skeleton for the implementation of different types of lattices of arbitrary rank. More...

class	IntLatticeBasis
	This class represents a lattice and its basis and offers tools to do basic manipulations on lattice bases. More...

class	Lacunary
	This class implements sets of lacunary indices. More...

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

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

class	LatticeAnalysis
	This class gathers other classes of LatticeTester to create an object performing tests on lattices. More...

class	LatticeTesterConfig
	This class is used to save the configuration of a lattice test. More...

class	NormaBestLat
	This class implements the best theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in lattices. More...

class	NormaLaminated
	This class implements theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in laminated lattices. More...

class	Normalizer
	Classes which inherit from this base class are used in implementing bounds on the length of the shortest nonzero vector in a lattice [3] . More...

class	NormaMinkL1
	This class implements theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in space. More...

class	NormaMinkowski
	This class implements Minkowski’s theoretical bounds on the length of the shortest nonzero vector in a lattice. More...

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

class	NormaRogers
	This class implements the Rogers bounds on the density of sphere packing. More...

class	OrderDependentWeights
	Order-dependent weights. More...

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

class	PODWeights
	Product and order-dependent (POD) weights. More...

class	ProductWeights
	Product weights. More...

class	ProjectionDependentWeights
	Projection-dependent weights. More...

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

class	Rank1Lattice
	This class implements a general rank 1 lattice basis. More...

class	Reducer
	This class implements (or wraps from NTL) all the functions that are needed to reduce a basis. More...

struct	specLatticeAnalysis
	This structure specializes certain members of LatticeAnalysis. More...

struct	specLatticeAnalysis< NTL::ZZ, NTL::ZZ, Dbl, RedDbl >

struct	specLatticeAnalysis< std::int64_t, std::int64_t, Dbl, RedDbl >

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

class	UniformWeights
	This class is used to implement the same weight for all projections. More...

class	Weights
	Abstract weights class. More...

Typedefs
typedef double	Weight
	Scalar weight type. More...

Enumerations
enum	NormType { SUPNORM = 1, L1NORM = 2, L2NORM = 3, ZAREMBANORM = 4 }
	Indicates which norm is used to measure the length of vectors. More...

enum	OutputType { TERMINAL, RES, TEX, GEN }
	Indicates in which form and where the results will be sent. More...

enum	PrecisionType { DOUBLE, QUADRUPLE, EXPONENT, ARBITRARY, EXACT }
	Indicates in which precision the NTL algorithms will be perfoms : `FP` – double `QP` – quad_float (quasi quadruple precision) this is useful when roundoff errors can cause problems `XD` – xdouble (extended exponent doubles) this is useful when numbers get too big `RR` – RR (arbitrary precision floating point) this is useful for large precision and magnitudes Generally speaking, the choice FP will be the fastest, but may be prone to roundoff errors and/or overflow.

enum	PrimeType { UNKNOWN, PRIME, PROB_PRIME, COMPOSITE }
	Indicates whether an integer is prime, probably prime, composite or its status is unknown (or don’t care).

enum	CriterionType { SPECTRAL, BEYER, PALPHA, BOUND_JS }
	Gives the merit criterion for ranking generators or lattices. More...

enum	NormaType { BESTLAT, LAMINATED, ROGERS, MINKOWSKI, MINKL1, PALPHA_N, NORMA_GENERIC, L1, L2 }
	Indicates which normalization is used to compute \(S_t\) in the spectral test, for each dimension \(t\). More...

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

enum	PreReductionType { BKZ, PreRedDieter, LenstraLL, NOPRERED }
	Indicates the Prereduction Type (BKZ, LenstraLL, ...) used before applying the Branch and Bound procedure.

Functions
int	getDir (std::string dir, std::vector< std::string > &files)

void	eraseExtension (std::vector< std::string > &files)

void	printFileNames (std::vector< std::string > &files)

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	ShortestVector (BasIntMat matrix, NormType norm, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	This function allows computation of the shortest non-zero vector in a lattice, according to the selected norm. More...

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	ShortestVector (BasIntMat matrix, NormType norm, std::int64_t maxNodesBB, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	Same thing as before but with the possibility to set a different value for the variable maxNodesBB.

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	FigureOfMerit (BasIntMat matrix, NormaType normalizerType, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	This function compute the Figure of Merit to a given matrix, according to a normalization criteria. More...

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	FigureOfMerit (BasIntMat matrix, NormaType normalizerType, std::int64_t maxNodesBB, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	Same thing as before but with the possibility to set a different value for the variable maxNodesBB.

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
bool	MinkowskiReduction (BasIntMat &matrix, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	This function reduces a basis to a Minkowski-reduced basis. More...

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
bool	MinkowskiReduction (BasIntMat &matrix, std::int64_t maxNodesBB, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	Same thing as before but with the possibility to set a different value for the variable maxNodesBB.

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	FigureOfMeritBeyer (BasIntMat matrix, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	This function compute the Figure of Merit to a given matrix, according to the Beyer criteria. More...

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >
double	FigureOfMeritBeyer (BasIntMat matrix, std::int64_t maxNodesBB, PreReductionType preRed=BKZ, PrecisionType doublePrecision=DOUBLE, double fact=0.999, int blocksize=20)
	Same thing as before but with the possibility to set a different value for the variable maxNodesBB.

std::int64_t	lFactorial (int 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 (int n, double x)
	Evaluates the Bernoulli polynomial \(B_n(x)\) of degree \(n\) at \(x\). More...

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 \[ \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.

double	FourierC1 (double x, std::int64_t n)
	Computes and returns the value of the series (see [15]) \[ S(x, n) = \sum_{j=1}^{n} \frac{\cos(2\pi j x)}{j}. \] Restrictions: \(n>0\) and \(0 \le x \le 1\).

double	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. More...

template<typename Int , typename BasIntMat >
void	initNorm (LatticeTesterConfig< Int, BasIntMat > &config)
	Sets the norm in config depending on it's normalizer.

void	negativeCholeski ()

template<typename T >
void	swap9 (T &x, T &y)
	Swaps the values of `x` and `y`.

template<class K , class T , class C , class A >
std::ostream &	operator<< (std::ostream &out, const std::map< K, T, C, A > &x)
	}.

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

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

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

toString functions
Useful functions for printing the `enum` constants in this module. Returns the `enum` constants in this module as strings.
std::string	toStringNorm (NormType)

std::string	toStringPrime (PrimeType)

std::string	toStringCriterion (CriterionType)

std::string	toStringNorma (NormaType)

std::string	toStringCalc (CalcType)

std::string	toStringPreRed (PreReductionType)

std::string	toStringOutput (OutputType)

std::string	toStringPrecision (PrecisionType)

Random numbers
double	RandU01 ()
	Returns a random number in \([0, 1)\). More...

int	RandInt (int i, int j)
	Return a random integer in \([i, j]\). More...

std::uint64_t	RandBits (int s)
	Returns random blocks of \(s\) bits ( \(s\)-bit integers).

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

std::int64_t	IsOdd (const std::int64_t &x)
	Returns 1 if \(x\) is odd, and 0 otherwise.

bool	IsZero (const std::int64_t &x)
	Return `true` if \(x = 0\).

void	clear (double &x)
	Sets \(x\) to 0.

void	clear (std::int64_t &x)
	Sets \(x\) to 0.

void	set9 (std::int64_t &x)
	Sets \(x\) to 1.

void	set9 (NTL::ZZ &x)
	Sets \(x\) to 1.

Mathematical functions
std::int64_t	power (std::int64_t p, std::int64_t i)
	Returns \(p^i\).

void	power2 (std::int64_t &z, std::int64_t i)
	Sets \(z = 2^i\).

void	power2 (NTL::ZZ &z, std::int64_t i)
	Sets \(z = 2^i\).

double	mysqrt (double x)
	Returns \(\sqrt{x}\) for \(x\ge0\), and \(-1\) for \(x < 0\).

double	SqrRoot (double x)
	Returns \(\sqrt{x}\). More...

template<typename T >
double	Lg (const T &x)
	Logarithm of \(x\) in base 2.

double	Lg (std::int64_t x)
	Logarithm of \(x\) in base 2.

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

template<typename T >
std::int64_t	sign (const T &x)
	Returns 1, 0 or \(-1\) depending on whether \(x> 0\), \(x= 0\) or \(x< 0\) respectively.

template<typename Real >
Real	Round (Real x)
	Rounds to the nearest integer value.

std::int64_t	Factorial (int t)
	Calculates \(t!\), the factorial of \(t\).

Division and remainder
For negative operands, the `/` and `%` operators do not give the same results for NTL large integers `ZZ` and for primitive types `int` and `std::int64_t`. The negative quotient differs by 1 and the remainder also differs. Thus the following small `inline` functions for division and remainder. 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.
template<typename Int >
void	Quotient (const Int &a, const Int &b, Int &q)
	Computes \(q = a/b\) by dropping the fractionnal part, i.e. More...

void	Quotient (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &q)
	Computes \(q = a/b\) by dropping the fractionnal part, i.e. More...

template<typename Real >
void	Modulo (const Real &a, const Real &b, Real &r)

void	Modulo (const std::int64_t &a, const std::int64_t &b, std::int64_t &r)
	Computes the "positive" remainder \(r = a \bmod b\), i.e. More...

void	Modulo (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &r)
	Computes the "positive" remainder \(r = a \bmod b\), i.e. More...

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\). More...

void	Divide (std::int64_t &q, std::int64_t &r, const std::int64_t &a, const std::int64_t &b)
	Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0. More...

void	Divide (NTL::ZZ &q, NTL::ZZ &r, const NTL::ZZ &a, const NTL::ZZ &b)
	Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0. More...

void	div (std::int64_t &a, const std::int64_t &b, const std::int64_t &d)
	Integer division: \(a = b/d\).

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\).

void	DivideRound (const std::int64_t &a, const std::int64_t &b, std::int64_t &q)
	Computes \(a/b\), rounds the result to the nearest integer and returns the result in \(q\).

void	DivideRound (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &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\). More...

template<typename Int >
void	Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &E, Int &F, Int &G)
	For given \(a\) and \(b\), returns the values \(C\), \(D\), \(E\), \(F\) and \(G\) such that: \begin{align} C a + D b & = G = \mbox{GCD } (a,b) \\ E a + F b & = 0. \end{align} .

Vectors
template<typename Real >
void	CreateVect (Real *&A, int d)
	Allocates memory for the vector \(A\) of dimensions \(d\) 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	CreateVect (Vect &A, int d)
	Creates the vector \(A\) of dimensions \(d+1\) and initializes its elements to 0.

template<typename Vect >
void	DeleteVect (Vect &A)
	Frees the memory used by the vector \(A\).

template<typename Real >
void	SetZero (Real *A, int d)
	Sets components \([0..d-1]\) of \(A\) to 0.

template<typename Vect >
void	SetZero (Vect &A, int d)
	Sets components \([0..d-1]\) of \(A\) to 0.

template<typename Real >
void	SetValue (Real *A, int d, const Real &x)
	Sets all components \([0..d]\) of \(A\) to the value \(x\).

template<typename Vect >
std::string	toString (const Vect &A, int c, int d, const char *sep)
	Prints components \([c..d-1]\) of vector \(A\) as a string. More...

template<typename Vect >
std::string	toString (const Vect &A, int c, int d)
	Prints components \([c..d]\) of vector \(A\) as a string.

template<typename Vect >
std::string	toString (const Vect &A, int d)
	Prints components \([0..d-1]\) of vector \(A\) as a string.

template<typename Int , typename Vect1 , typename Vect2 , typename Scal >
void	ProdScal (const Vect1 &A, const Vect2 &B, int n, Scal &D)
	Computes the scalar product of vectors \(A\) and \(B\), using components \([0..n-1]\), and puts the result in \(D\). More...

template<typename IntVec >
void	Invert (const IntVec &A, IntVec &B, int n)
	Transforms the polynomial \(A_0 + A_1x^1 + \cdots+ A_nx^n\) into \(x^n - A_1x^{n-1} - \cdots- A_n\). More...

template<typename Vect , typename Scal >
void	CalcNorm (const Vect &V, int n, Scal &S, NormType norm)
	Computes the `norm` norm of vector \(V\), using components \([1..n]\), and puts the result in \(S\).

template<typename Vect >
void	CopyVect (Vect &A, const Vect &B, int n)
	Copies vector \(B\) into vector \(A\) using components \([0..n-1]\).

template<typename Vect1 , typename Vect2 , typename Scal >
void	ModifVect (Vect1 &A, const Vect2 &B, Scal x, int n)
	Adds vector \(B\) multiplied by \(x\) to vector \(A\) using components \([0..n-1]\), and puts the result in \(A\).

template<typename Vect >
void	ChangeSign (Vect &A, int n)
	Changes the sign of the components \([0..n-1]\) of vector \(A\).

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

Matrices
template<typename Real >
void	CreateMatr (Real **&A, int d)
	Allocates memory for the square matrix \(A\) of dimensions \((d+1)\times(d+1)\). More...

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

template<typename Real >
void	CreateMatr (Real **&A, int line, int col)
	Allocates memory for the matrix \(A\) of dimensions (`line`) \(\times\) (`col`). More...

template<typename Real >
void	DeleteMatr (Real **&A, int line, int col)
	Frees the memory used by the matrix \(A\).

template<typename IntMat >
void	CreateMatr (IntMat &A, int d)
	Creates the square matrix \(A\) of dimensions \(d\times d\) and initializes its elements to 0.

template<typename IntMat >
void	CreateMatr (IntMat &A, int line, int col)
	Creates the matrix \(A\) of dimensions (`line`) \(\times\) (`col`). More...

template<typename IntMat >
void	DeleteMatr (IntMat &A)
	Deletes the matrix \(A\).

template<typename Matr >
void	CopyMatr (Matr &A, const Matr &B, int n)
	As above. More...

template<typename Matr >
void	CopyMatr (Matr &A, const Matr &B, int line, int col)
	As above.

template<typename MatT >
std::string	toStr (const MatT &mat, int d1, int d2)
	Transforms `mat` into a string. More...

template<typename Matr , typename Int >
bool	CheckTriangular (const Matr &A, int dim, const Int &m)
	Checks that square matrix \(A\) is upper triangular (modulo \(m\)) for dimensions 1 to `dim`.

template<typename Matr , typename Int >
void	Triangularization (Matr &W, Matr &V, int lin, int col, const Int &m)
	Performs an integer triangularization operation modulo \(m\) on the matrix \(W\) to obtain an upper triangular matrix \(V\), dual to \(W\). More...

template<typename Matr , typename Int >
void	CalcDual (const Matr &A, Matr &B, int d, const Int &m)
	Calculates the \(m\)-dual of the matrix `A`. More...

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

Variables
const std::array< unsigned int, NB_PRIMES >	PRIMES_ARRAY

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

Scalar weight type.

Note: We could have used Weight, but it might be wise to leave this typedef in case we decide to use std::int64_t Weight at some point.

Enumeration Type Documentation

◆ CalcType

enum LatticeTester::CalcType

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

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.

◆ CriterionType

enum LatticeTester::CriterionType

Gives the merit criterion for ranking generators or lattices.

BEYER: the figure of merit is the Beyer quotient \(Q_T\).
SPECTRAL: the figure of merit \(S_T\) is based on the spectral test.
PALPHA: the figure of merit is based on \(P_{\alpha}\).
BOUND_JS: the figure of merit is based on the Joe-Sinescu bound [29] .

◆ NormaType

enum LatticeTester::NormaType

Indicates which normalization is used to compute \(S_t\) in the spectral test, for each dimension \(t\).

BESTLAT: the value used for \(d_t^*\) corresponds to the best lattice.
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.
MINKOWSKI: 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.
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.
PALPHA_N: the case of the \(P_{\alpha}\) test.
NORMA_GENERIC: the trivial normalization (= 1) used for the generic case when no useful normalization constant is known.

◆ NormType

enum LatticeTester::NormType

Indicates which norm is used 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|)\).

◆ OutputType

enum LatticeTester::OutputType

Indicates in which form and where the results will be sent.

TERMINAL: the results will appear only on the terminal screen.
RES: the results will be in plain text format and sent to a file with extension .res.
TEX: the results will be in LaTeX format and sent to a file with extension .tex.
GEN: the results will be sent to a file with extension .gen.

Function Documentation

◆ BernoulliPoly()

double LatticeTester::BernoulliPoly	(	int	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,
		int	d,
		const Int &	m
	)

Calculates the \(m\)-dual of the matrix A.

The result is placed in the matrix B. Only the first \(d\) lines and columns are considered.

The vectors of the basis (lines of A) need to verify the properties (i), (ii) (iii), (iv) as described in the article: R. Couture and P L'Ecuyer, Orbits and lattices for linear random number generators with composite moduli, Mathematics of Computation, Volume 65, Number 213, bottom of page 199.

References clear(), and DivideRound().

◆ CopyMatr()

template<typename Matr >

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

inline

As above.

Copies matrix \(B\) into matrix \(A\).

Referenced by LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::copyBasis().

◆ CreateMatr() [1/3]

template<typename Real >

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

inline

Allocates memory for the square matrix \(A\) of dimensions \((d+1)\times(d+1)\).

Initializes its elements to 0.

◆ CreateMatr() [2/3]

template<typename Real >

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

inline

Allocates memory for the matrix \(A\) of dimensions (line) \(\times\) (col).

Initializes its elements to 0.

◆ CreateMatr() [3/3]

template<typename IntMat >

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

inline

Creates the matrix \(A\) of dimensions (line) \(\times\) (col).

Initializes its elements to 0.

◆ Divide() [1/3]

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|\).

◆ Divide() [2/3]

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

inline

Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0.

The remainder can be negative. One always has \(a = qb + r\) and \(|r| < |b|\). Example:

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

◆ Divide() [3/3]

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

inline

Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0.

The remainder can be negative. One always has \(a = qb + r\) and \(|r| < |b|\). Example:

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

◆ FigureOfMerit()

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >

double LatticeTester::FigureOfMerit	(	BasIntMat	matrix,
		NormaType	normalizerType,
		PreReductionType	preRed = `BKZ`,
		PrecisionType	doublePrecision = `DOUBLE`,
		double	fact = `0.999`,
		int	blocksize = `20`
	)

This function compute the Figure of Merit to a given matrix, according to a normalization criteria.

It first computes the shortest non-zero vector using the above functions. It then normalizes this value. Returns -1.0 if there was an error in Branch-and-Bound procedure while calculating the length of shortest non-zero vector. Return the figure of merit otherwise.

◆ FigureOfMeritBeyer()

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >

double LatticeTester::FigureOfMeritBeyer	(	BasIntMat	matrix,
		PreReductionType	preRed = `BKZ`,
		PrecisionType	doublePrecision = `DOUBLE`,
		double	fact = `0.999`,
		int	blocksize = `20`
	)

This function compute the Figure of Merit to a given matrix, according to the Beyer criteria.

It first computes the Minkowski-reduced basis of the lattice and then makes the quotient of shortest over std::int64_test vector. Returns -1.0 if there was an error in Branch-and-Bound procedure while calculating the Minkowski-reduced basis. Return the figure of merit otherwise.

References NTL::conv(), LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::getVecNorm(), MyExit(), and LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateScalL2Norm().

◆ FourierE1()

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\).

Remarks: Richard: Il y a déjà des fonctions GCD dans NTL, pour les std::int64_t et les ZZ (voir fichier ZZ.h)

Referenced by LatBuilder::GenSeq::GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV >::GeneratingValues().

◆ Invert()

template<typename IntVec >

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

inline

Transforms the polynomial \(A_0 + A_1x^1 + \cdots+ A_nx^n\) into \(x^n - A_1x^{n-1} - \cdots- A_n\).

The result is put in \(B\).

◆ MinkowskiReduction()

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >

bool LatticeTester::MinkowskiReduction	(	BasIntMat &	matrix,
		PreReductionType	preRed = `BKZ`,
		PrecisionType	doublePrecision = `DOUBLE`,
		double	fact = `0.999`,
		int	blocksize = `20`
	)

This function reduces a basis to a Minkowski-reduced basis.

Such basis has strong properties regarding the length of its vectors but will require a huge running time, especially when the dimension of the basis increases. Such Minkowski-reduced basis is usefull, for example, to calculate a Beyer quotient (as implemented in FigureOfMerit()).

References LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::getIntLatticeBasis(), MyExit(), and LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::reductMinkowski().

◆ Modulo() [1/2]

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

inline

Computes the "positive" remainder \(r = a \bmod b\), i.e.

such that \(0 \le r < b\). Example:

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

◆ Modulo() [2/2]

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

inline

Computes the "positive" remainder \(r = a \bmod b\), i.e.

such that \(0 \le r < b\). Example:

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

◆ MyExit()

void LatticeTester::MyExit	(	int	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.

◆ operator<<() [1/2]

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<<() [2/2]

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 ].

◆ ProdScal()

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

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

inline

Computes the scalar product of vectors \(A\) and \(B\), using components \([0..n-1]\), and puts the result in \(D\).

THIS DOES NOT SEEM TO BE A VERY SAFE IMPLEMENTATION

References NTL::conv().

◆ Quotient() [1/2]

template<typename Int >

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

inline

Computes \(q = a/b\) by dropping the fractionnal part, i.e.

truncates towards 0. Example:

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

Referenced by Euclide(), and Triangularization().

◆ Quotient() [2/2]

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

inline

Computes \(q = a/b\) by dropping the fractionnal part, i.e.

truncates towards 0. Example:

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

◆ RandInt()

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

Return a random integer in \([i, j]\).

Numbers \(i\) and \(j\) can occur. Restriction: \(i < j\).

◆ RandU01()

double LatticeTester::RandU01 ( )

Returns a random number in \([0, 1)\).

The number has 53 random bits.

◆ SetSeed()

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

Sets the seed of the generator.

If not called, a default seed will be used.

◆ ShortestVector()

template<typename Int , typename BasInt , typename BasIntMat , typename Dbl , typename RedDbl >

double LatticeTester::ShortestVector	(	BasIntMat	matrix,
		NormType	norm,
		PreReductionType	preRed = `BKZ`,
		PrecisionType	doublePrecision = `DOUBLE`,
		double	fact = `0.999`,
		int	blocksize = `20`
	)

This function allows computation of the shortest non-zero vector in a lattice, according to the selected norm.

Many parameters can bet set by the user, otherwise the function work with default values. Returns -1.0 if there was an error in Branch-and-Bound procedure. Return the length of the shortest non-zero vector otherwise.

References LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::getMinLength(), MyExit(), LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redBKZ(), LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::redLLLNTL(), and LatticeTester::Reducer< Int, BasInt, Dbl, RedDbl >::shortestVector().

◆ SqrRoot()

double LatticeTester::SqrRoot ( double x )

inline

Returns \(\sqrt{x}\).

Remarks: Richard: Cette fonction est-elle encore utilisée?

Referenced by LatticeTester::IntFactor< Int >::isPrime().

◆ toStr()

template<typename MatT >

std::string LatticeTester::toStr	(	const MatT &	mat,
		int	d1,
		int	d2
	)

Transforms mat into a string.

Prints the first \(d1\) rows and \(d2\) columns. Indices start at 1. Elements with index 0 are not printed.

◆ toString()

template<typename Vect >

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

Prints components \([c..d-1]\) of vector \(A\) as a string.

Components are separated by string sep.

Referenced by toString(), and LatticeTester::Rank1Lattice< Int, BasInt, Dbl, RedDbl >::toStringCoef().

◆ Triangularization()

template<typename Matr , typename Int >

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

Performs an integer triangularization operation modulo \(m\) on the matrix \(W\) to obtain an upper triangular matrix \(V\), dual to \(W\).

However, the matrix \(W\) will be transformed too in order to preserve duality. Only the first lin lines and the first col columns of the matrices will be considered. The main idea is to transform a generating family of vectors into a basis (removing from the family the vectors that are linear combination of other vectors).

Refer to the article: R. Couture and P L'Ecuyer, Orbits and lattices for linear random number generators with composite moduli, Mathematics of Computation, Volume 65, Number 213, bottom of page 199.

References clear(), Euclide(), IsZero(), and Quotient().

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ Weight

Enumeration Type Documentation

◆ CalcType

◆ CriterionType

◆ NormaType

◆ NormType

◆ OutputType

Function Documentation

◆ BernoulliPoly()

◆ CalcDual()

◆ CopyMatr()

◆ CreateMatr() [1/3]

◆ CreateMatr() [2/3]

◆ CreateMatr() [3/3]

◆ Divide() [1/3]

◆ Divide() [2/3]

◆ Divide() [3/3]

◆ FigureOfMerit()

◆ FigureOfMeritBeyer()

◆ FourierE1()

◆ gcd()

◆ Invert()

◆ MinkowskiReduction()

◆ Modulo() [1/2]

◆ Modulo() [2/2]

◆ MyExit()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ ProdScal()

◆ Quotient() [1/2]

◆ Quotient() [2/2]

◆ RandInt()

◆ RandU01()

◆ SetSeed()

◆ ShortestVector()

◆ SqrRoot()

◆ toStr()

◆ toString()

◆ Triangularization()