#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <type_traits>
#include <NTL/tools.h>
#include <NTL/fileio.h>
#include <NTL/vector.h>
#include <NTL/matrix.h>
#include <NTL/vec_double.h>
#include <NTL/ZZ.h>
#include <NTL/LLL.h>
#include <latticetester/Util.h>

Macros
#define	TR_BND (NTL_FDOUBLE_PRECISION/2.0)

Typedefs
typedef NTL::vector< int64_t >	vector64
	This module contains a modified version of the `LLL_FP` module of NTL.

Functions
template<typename Int , typename IntMat >
NTL_OPEN_NNS long	LLL_FPInt (IntMat &B, const double delta=0.99, long r=0, long c=0, NTL::vector< double > *sqlen=0)
	This function is similar to `LLL_FP` in NTL, but only the first `r` rows and first `c` columns of the matrix `B` are considered, and a basis is built for the lattice generated by these (partial) rows.

template<typename Int , typename IntMat >
long	BKZ_FPInt (IntMat &BB, const double delta=0.99, long blocksize=10, long prune=0, long r=0, long c=0, NTL::vector< double > *sqlen=0)
	This function is similar to `BKZ_FP` in NTL, with the same modifications as in LLL_FPInt above.

NTL_CLOSE_NNS static NTL_START_IMPL void	CheckFinite (double *p)

static double	max_abs (double *v, long n)

static double	InnerProductD (double a, double b, long n)

template<typename Int , typename IntVec >
static void	InnerProductV (Int &prod, const IntVec &a, const IntVec &b, long n)

template<typename Int , typename IntVec >
void	InnerProductV (Int &prod, const IntVec &a, const IntVec &b, long n)

template<>
void	InnerProductV (int64_t &prod, const NTL::Vec< int64_t > &a, const NTL::Vec< int64_t > &b, long n)

template<>
void	InnerProductV (ZZ &prod, const NTL::Vec< ZZ > &a, const NTL::Vec< ZZ > &b, long n)

static void	InnerProductR (RR &xx, const vec_RR &a, const vec_RR &b, long n)

static void	RowTransformStartInt (double a, long in_a, long &in_float, long n)

template<typename IntVec >
static void	RowTransformFinishInt (IntVec &A, double a, long in_a, long n)

template<typename Int , typename IntVec >
static void	RowTransformInt (IntVec &A, IntVec &B, const Int &MU1, long n)

template<>
void	RowTransformInt (vec_ZZ &A, vec_ZZ &B, const ZZ &MU1, long n)

template<typename Int , typename IntVec >
static void	RowTransformInt (IntVec &A, IntVec &B, const Int &MU1, long n, double a, double b, long *in_a, double &max_a, double max_b, long &in_float)

template<>
void	RowTransformInt (NTL::Vec< long > &A, NTL::Vec< long > &B, const int64_t &MU1, long n, double a, double b, long *in_a, double &max_a, double max_b, int64_t &in_float)

template<>
void	RowTransformInt (NTL::Vec< ZZ > &A, NTL::Vec< ZZ > &B, const NTL::ZZ &MU1, long n, double a, double b, long *in_a, double &max_a, double max_b, long &in_float)

template<typename Int , typename IntVec >
static void	RowTransformAdd (IntVec &A, IntVec &B, const Int &MU1, long n)

template<>
void	RowTransformAdd (NTL::Vec< int64_t > &A, NTL::Vec< int64_t > &B, const int64_t &MU1, long n)

template<>
void	RowTransformAdd (vec_ZZ &A, vec_ZZ &B, const ZZ &MU1, long n)

template<typename Int , typename IntMat >
static void	ComputeGSInt (IntMat &B, double B1, double mu, double b, double c, long k, long n, double bound, long st, double *buf)

static void	init_red_fudge ()

static void	inc_red_fudge ()

template<typename IntMat >
void	printBB1 (IntMat &B, double **B1, long m)

void	ComputeGSInt (const mat_ZZ &B, mat_RR &B1, mat_RR &mu, vec_RR &b, vec_RR &c, long k, long n, const RR &bound, long st, vec_RR &buf, const RR &bound2)

template<typename Int , typename IntMat >
static void	RR_GSInt (IntMat &B, double B1, double mu, double b, double c, double *buf, long prec, long rr_st, long k, long m_orig, long n, mat_RR &rr_B1, mat_RR &rr_mu, vec_RR &rr_b, vec_RR &rr_c)

template<>
void	RR_GSInt< long, NTL::matrix< long > > (NTL::matrix< long > &B, double B1, double mu, double b, double c, double *buf, long prec, long rr_st, long k, long m_orig, long n, mat_RR &rr_B1, mat_RR &rr_mu, vec_RR &rr_b, vec_RR &rr_c)

template<>
void	RR_GSInt< NTL::ZZ, mat_ZZ > (mat_ZZ &B, double B1, double mu, double b, double c, double *buf, long prec, long rr_st, long k, long m_orig, long n, mat_RR &rr_B1, mat_RR &rr_mu, vec_RR &rr_b, vec_RR &rr_c)

void	ComputeGSInt (const mat_ZZ &B, mat_RR &mu, vec_RR &c, long m, long n)

template<typename Int , typename IntMat >
static long	ll_LLL_FPInt (IntMat &B, double delta, double B1, double mu, double b, double c, long m, long n, long init_k, long quit)

template<>
int64_t	ll_LLL_FPInt< long, matrix< long > > (matrix< int64_t > &B, double delta, double B1, double mu, double b, double c, int64_t m, int64_t n, int64_t init_k, long quit)

template<typename Int , typename IntMat >
long	ll_LLL_FPInt (IntMat &B, double delta, double B1, double mu, double b, double c, long m, long n, long init_k, long quit)

template<typename Int , typename IntMat >
long	LLL_FPInt (IntMat &B, double delta, long m, long n, NTL::vector< double > *sqlen)
	This function is similar to `LLL_FP` in NTL, but only the first `r` rows and first `c` columns of the matrix `B` are considered, and a basis is built for the lattice generated by these (partial) rows.

static void	ComputeBKZConstant (long beta, long p)

static void	ComputeBKZThresh (double *c, long beta)

template<typename Int , typename IntMat >
long	BKZ_FPInt (IntMat &BB, double delta, long beta, long prune, long m, long n, vector< double > *sqlen)

Variables
static NTL_CHEAP_THREAD_LOCAL double	red_fudge = 0

static NTL_CHEAP_THREAD_LOCAL long	log_red = 0

static NTL_CHEAP_THREAD_LOCAL unsigned long	NumSwaps = 0

static vec_double	BKZConstant

static vec_double	BKZThresh

Macro Definition Documentation

◆ TR_BND

#define TR_BND (NTL_FDOUBLE_PRECISION/2.0)

Typedef Documentation

◆ vector64

typedef NTL::vector<int64_t> vector64

This module contains a modified version of the LLL_FP module of NTL.

With the modified functions, the basis entries are in Int, which can be either int64_t or ZZ. We can also apply LLL or BKZ only to a submatrix (first r rows and c columns) of the matrix B that is passed in and returned. The returned basis will have c columns and at most max(r,c) rows (the rank of the basis matrix), so it may not occupy the entire space in B. With this flexibility, we can reserve a large block of memory for the matrix B and reuse this same block (the same object B) for thousands or millions of lattices that we want to analyze, even if the bases have different dimensions.

Another addition is the possibility to recover an array sqlen that gives the square Euclidean lengths of the basis vectors, in double. This array is maintained in the LLL_FP functions of NTL, but it is hidden in the implementation and not accessible from outside. In IntLattice, these lengths are maintained in a RealVec object. In this module, we assume that Real = double.

Each function returns the dimension of the computed basis (number of independent rows). This basis is always returned in the upper-left corner of the matrix B. This differs from the LLL_FP functions, which returns the zero vectors at the top.

Function Documentation

◆ BKZ_FPInt() [1/2]

template<typename Int , typename IntMat >

long BKZ_FPInt	(	IntMat &	BB,
		const double	delta = 0.99,
		long	blocksize = 10,
		long	prune = 0,
		long	r = 0,
		long	c = 0,
		NTL::vector< double > *	sqlen = 0 )

This function is similar to BKZ_FP in NTL, with the same modifications as in LLL_FPInt above.

◆ BKZ_FPInt() [2/2]

template<typename Int , typename IntMat >

long BKZ_FPInt	(	IntMat &	BB,
		double	delta,
		long	beta,
		long	prune,
		long	m,
		long	n,
		vector< double > *	sqlen )

◆ CheckFinite()

NTL_CLOSE_NNS static NTL_START_IMPL void CheckFinite ( double * p )

inlinestatic

◆ ComputeBKZConstant()

static void ComputeBKZConstant	(	long	beta,
		long	p )

static

◆ ComputeBKZThresh()

static void ComputeBKZThresh	(	double *	c,
		long	beta )

static

◆ ComputeGSInt() [1/3]

void ComputeGSInt	(	const mat_ZZ &	B,
		mat_RR &	B1,
		mat_RR &	mu,
		vec_RR &	b,
		vec_RR &	c,
		long	k,
		long	n,
		const RR &	bound,
		long	st,
		vec_RR &	buf,
		const RR &	bound2 )

◆ ComputeGSInt() [2/3]

void ComputeGSInt	(	const mat_ZZ &	B,
		mat_RR &	mu,
		vec_RR &	c,
		long	m,
		long	n )

◆ ComputeGSInt() [3/3]

template<typename Int , typename IntMat >

static void ComputeGSInt	(	IntMat &	B,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		long	k,
		long	n,
		double	bound,
		long	st,
		double *	buf )

static

◆ inc_red_fudge()

static void inc_red_fudge ( )

static

◆ init_red_fudge()

static void init_red_fudge ( )

static

◆ InnerProductD()

static double InnerProductD	(	double *	a,
		double *	b,
		long	n )

static

◆ InnerProductR()

static void InnerProductR	(	RR &	xx,
		const vec_RR &	a,
		const vec_RR &	b,
		long	n )

static

◆ InnerProductV() [1/4]

template<typename Int , typename IntVec >

static void InnerProductV	(	Int &	prod,
		const IntVec &	a,
		const IntVec &	b,
		long	n )

static

◆ InnerProductV() [2/4]

template<typename Int , typename IntVec >

void InnerProductV	(	Int &	prod,
		const IntVec &	a,
		const IntVec &	b,
		long	n )

◆ InnerProductV() [3/4]

template<>

void InnerProductV	(	int64_t &	prod,
		const NTL::Vec< int64_t > &	a,
		const NTL::Vec< int64_t > &	b,
		long	n )

◆ InnerProductV() [4/4]

template<>

void InnerProductV	(	ZZ &	prod,
		const NTL::Vec< ZZ > &	a,
		const NTL::Vec< ZZ > &	b,
		long	n )

◆ ll_LLL_FPInt() [1/2]

template<typename Int , typename IntMat >

static long ll_LLL_FPInt	(	IntMat &	B,
		double	delta,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		long	m,
		long	n,
		long	init_k,
		long	quit )

static

◆ ll_LLL_FPInt() [2/2]

template<typename Int , typename IntMat >

long ll_LLL_FPInt	(	IntMat &	B,
		double	delta,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		long	m,
		long	n,
		long	init_k,
		long	quit )

◆ ll_LLL_FPInt< long, matrix< long > >()

template<>

int64_t ll_LLL_FPInt< long, matrix< long > >	(	matrix< int64_t > &	B,
		double	delta,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		int64_t	m,
		int64_t	n,
		int64_t	init_k,
		long	quit )

◆ LLL_FPInt() [1/2]

template<typename Int , typename IntMat >

NTL_OPEN_NNS long LLL_FPInt	(	IntMat &	B,
		const double	delta = 0.99,
		long	r = 0,
		long	c = 0,
		NTL::vector< double > *	sqlen = 0 )

This function is similar to LLL_FP in NTL, but only the first r rows and first c columns of the matrix B are considered, and a basis is built for the lattice generated by these (partial) rows.

The other elements of B are ignored. The basis is returned in the upper left corner of B, with the shortest basis vector always in the first row. If r=0, then all the rows of the IntMat object are taken. If c=0, then all the columns are taken. The square lengths of the returned basis vectors are also returned in the double vector sqlen, in sqlen[0],..., sqlen[d-1], if this vector given. The indices of B and sqlen start at 0. The function returns the dimension of the computed basis (the number of independent rows).

◆ LLL_FPInt() [2/2]

template<typename Int , typename IntMat >

long LLL_FPInt	(	IntMat &	B,
		const double	delta = 0.99,
		long	r = 0,
		long	c = 0,
		NTL::vector< double > *	sqlen = 0 )

This function is similar to LLL_FP in NTL, but only the first r rows and first c columns of the matrix B are considered, and a basis is built for the lattice generated by these (partial) rows.

The other elements of B are ignored. The basis is returned in the upper left corner of B, with the shortest basis vector always in the first row. If r=0, then all the rows of the IntMat object are taken. If c=0, then all the columns are taken. The square lengths of the returned basis vectors are also returned in the double vector sqlen, in sqlen[0],..., sqlen[d-1], if this vector given. The indices of B and sqlen start at 0. The function returns the dimension of the computed basis (the number of independent rows).

◆ max_abs()

static double max_abs	(	double *	v,
		long	n )

static

◆ printBB1()

template<typename IntMat >

void printBB1	(	IntMat &	B,
		double **	B1,
		long	m )

◆ RowTransformAdd() [1/3]

template<typename Int , typename IntVec >

static void RowTransformAdd	(	IntVec &	A,
		IntVec &	B,
		const Int &	MU1,
		long	n )

static

◆ RowTransformAdd() [2/3]

template<>

void RowTransformAdd	(	NTL::Vec< int64_t > &	A,
		NTL::Vec< int64_t > &	B,
		const int64_t &	MU1,
		long	n )

◆ RowTransformAdd() [3/3]

template<>

void RowTransformAdd	(	vec_ZZ &	A,
		vec_ZZ &	B,
		const ZZ &	MU1,
		long	n )

◆ RowTransformFinishInt()

template<typename IntVec >

static void RowTransformFinishInt	(	IntVec &	A,
		double *	a,
		long *	in_a,
		long	n )

static

◆ RowTransformInt() [1/5]

template<typename Int , typename IntVec >

static void RowTransformInt	(	IntVec &	A,
		IntVec &	B,
		const Int &	MU1,
		long	n )

static

◆ RowTransformInt() [2/5]

template<typename Int , typename IntVec >

static void RowTransformInt	(	IntVec &	A,
		IntVec &	B,
		const Int &	MU1,
		long	n,
		double *	a,
		double *	b,
		long *	in_a,
		double &	max_a,
		double	max_b,
		long &	in_float )

static

◆ RowTransformInt() [3/5]

template<>

void RowTransformInt	(	NTL::Vec< long > &	A,
		NTL::Vec< long > &	B,
		const int64_t &	MU1,
		long	n,
		double *	a,
		double *	b,
		long *	in_a,
		double &	max_a,
		double	max_b,
		int64_t &	in_float )

◆ RowTransformInt() [4/5]

template<>

void RowTransformInt	(	NTL::Vec< ZZ > &	A,
		NTL::Vec< ZZ > &	B,
		const NTL::ZZ &	MU1,
		long	n,
		double *	a,
		double *	b,
		long *	in_a,
		double &	max_a,
		double	max_b,
		long &	in_float )

◆ RowTransformInt() [5/5]

template<>

void RowTransformInt	(	vec_ZZ &	A,
		vec_ZZ &	B,
		const ZZ &	MU1,
		long	n )

◆ RowTransformStartInt()

static void RowTransformStartInt	(	double *	a,
		long *	in_a,
		long &	in_float,
		long	n )

static

◆ RR_GSInt()

template<typename Int , typename IntMat >

static void RR_GSInt	(	IntMat &	B,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		double *	buf,
		long	prec,
		long	rr_st,
		long	k,
		long	m_orig,
		long	n,
		mat_RR &	rr_B1,
		mat_RR &	rr_mu,
		vec_RR &	rr_b,
		vec_RR &	rr_c )

static

◆ RR_GSInt< long, NTL::matrix< long > >()

template<>

void RR_GSInt< long, NTL::matrix< long > >	(	NTL::matrix< long > &	B,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		double *	buf,
		long	prec,
		long	rr_st,
		long	k,
		long	m_orig,
		long	n,
		mat_RR &	rr_B1,
		mat_RR &	rr_mu,
		vec_RR &	rr_b,
		vec_RR &	rr_c )

◆ RR_GSInt< NTL::ZZ, mat_ZZ >()

template<>

void RR_GSInt< NTL::ZZ, mat_ZZ >	(	mat_ZZ &	B,
		double **	B1,
		double **	mu,
		double *	b,
		double *	c,
		double *	buf,
		long	prec,
		long	rr_st,
		long	k,
		long	m_orig,
		long	n,
		mat_RR &	rr_B1,
		mat_RR &	rr_mu,
		vec_RR &	rr_b,
		vec_RR &	rr_c )

Variable Documentation

◆ BKZConstant

vec_double BKZConstant

static

◆ BKZThresh

vec_double BKZThresh

static

◆ log_red

NTL_CHEAP_THREAD_LOCAL long log_red = 0

static

◆ NumSwaps

NTL_CHEAP_THREAD_LOCAL unsigned long NumSwaps = 0

static

◆ red_fudge

NTL_CHEAP_THREAD_LOCAL double red_fudge = 0

static

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ TR_BND

Typedef Documentation

◆ vector64

Function Documentation

◆ BKZ_FPInt() [1/2]

◆ BKZ_FPInt() [2/2]

◆ CheckFinite()

◆ ComputeBKZConstant()

◆ ComputeBKZThresh()

◆ ComputeGSInt() [1/3]

◆ ComputeGSInt() [2/3]

◆ ComputeGSInt() [3/3]

◆ inc_red_fudge()

◆ init_red_fudge()

◆ InnerProductD()

◆ InnerProductR()

◆ InnerProductV() [1/4]

◆ InnerProductV() [2/4]

◆ InnerProductV() [3/4]

◆ InnerProductV() [4/4]

◆ ll_LLL_FPInt() [1/2]

◆ ll_LLL_FPInt() [2/2]

◆ ll_LLL_FPInt< long, matrix< long > >()

◆ LLL_FPInt() [1/2]

◆ LLL_FPInt() [2/2]

◆ max_abs()

◆ printBB1()

◆ RowTransformAdd() [1/3]

◆ RowTransformAdd() [2/3]

◆ RowTransformAdd() [3/3]

◆ RowTransformFinishInt()

◆ RowTransformInt() [1/5]

◆ RowTransformInt() [2/5]

◆ RowTransformInt() [3/5]

◆ RowTransformInt() [4/5]

◆ RowTransformInt() [5/5]

◆ RowTransformStartInt()

◆ RR_GSInt()

◆ RR_GSInt< long, NTL::matrix< long > >()

◆ RR_GSInt< NTL::ZZ, mat_ZZ >()

Variable Documentation

◆ BKZConstant

◆ BKZThresh

◆ log_red

◆ NumSwaps

◆ red_fudge