fmpz_lll.h – LLL reduction¶
Description.
Parameter manipulation¶
These functions are used to initialise LLL context objects which are of the
type fmpz_lll_t
. These objects contain all information about the
options governing the reduction using this module’s functions including the
LLL parameters delta and eta, the representation type of the input matrix
(whether it is a lattice basis or a Gram matrix), and the type of Gram
matrix to be used during L^2 (approximate or exact).
-
void
fmpz_lll_context_init_default
(fmpz_lll_t fl)¶ Sets
fl->delta
,fl->eta
,fl->rt
andfl->gt
to their default values, 0.99, 0.51, \(Z_BASIS\) and \(APPROX\) respectively.
-
void
fmpz_lll_context_init
(fmpz_lll_t fl, double delta, double eta, rep_type rt, gram_type gt)¶ Sets
fl->delta
,fl->eta
,fl->rt
andfl->gt
todelta
,eta
,rt
andgt
(given as input) respectively.delta
andeta
are the L^2 parameters.delta
andeta
must lie in the intervals \((0.25, 1)\) and (0.5, sqrt{delta
}) respectively. The representation type is input usingrt
and can have the values \(Z_BASIS\) for a lattice basis and \(GRAM\) for a Gram matrix. The Gram type to be used during computation can be specified usinggt
which can assume the values \(APPROX\) and \(EXACT\). Note thatgt
has meaning only whenrt
is \(Z_BASIS\).
Random parameter generation¶
-
void
fmpz_lll_randtest
(fmpz_lll_t fl, flint_rand_t state)¶ Sets
fl->delta
andfl->eta
to random values in the interval \((0.25, 1)\) and (0.5, sqrt{delta
}) respectively.fl->rt
is set to \(GRAM\) or \(Z_BASIS\) andfl->gt
is set to \(APPROX\) or \(EXACT\) in a pseudo random way.
Heuristic dot product¶
-
double
fmpz_lll_heuristic_dot
(const double * vec1, const double * vec2, slong len2, const fmpz_mat_t B, slong k, slong j, slong exp_adj)¶ Computes the dot product of two vectors of doubles
vec1
andvec2
, which are respectivelydouble
approximations (up to scaling by a power of 2) to rowsk
andj
in the exact integer matrixB
. If massive cancellation is detected an exact computation is made.The exact computation is scaled by
2^{-exp_adj
}, whereexp_adj = r2 + r1
where \(r2\) is the exponent for rowj
and \(r1\) is the exponent for rowk
(i.e. rowj
is notionally thought of as being multiplied by \(2^{r2}\), etc.).The final dot product computed by this function is then notionally the return value times
2^{exp_adj
}.
The various Babai’s¶
-
int
fmpz_lll_check_babai
(int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s, d_mat_t appB, int *expo, fmpz_gram_t A, int a, int zeros, int kappamax, int n, const fmpz_lll_t fl)¶ Performs floating point size reductions of the
kappa
-th row ofB
by all of the previous rows, uses d_matsmu
andr
for storing the GSO data.U
is used to capture the unimodular transformations if it is not \(NULL\). Thedouble
arrays
will contain the size of thekappa
-th row if it were moved into position \(i\). The d_matappB
is an approximation ofB
with each row receiving an exponent stored inexpo
which gets populated only when needed. The d_matA->appSP
is an approximation of the Gram matrix whose entries are scalar products of the rows ofB
and is used whenfl->gt
== \(APPROX\). Whenfl->gt
== \(EXACT\) the fmpz_matA->exactSP
(the exact Gram matrix) is used. The indexa
is the smallest row index which will be reduced from thekappa
-th row. Indexzeros
is the number of zero rows in the matrix.kappamax
is the highest index which has been size-reduced so far, andn
is the number of columns you want to consider.fl
is an LLL (L^2) context object. The output is the value -1 if the process fails (usually due to insufficient precision) or 0 if everything was successful. These descriptions will be true for the future Babai procedures as well.
-
int
fmpz_lll_check_babai_heuristic_d
(int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s, d_mat_t appB, int *expo, fmpz_gram_t A, int a, int zeros, int kappamax, int n, const fmpz_lll_t fl)¶ Same as
fmpz_lll_check_babai()
but using the heuristic inner product rather than a purely floating point inner product. The heuristic will compute at full precision when there is cancellation.
-
int
fmpz_lll_check_babai_heuristic
(int kappa, fmpz_mat_t B, fmpz_mat_t U, mpf_mat_t mu, mpf_mat_t r, mpf *s, mpf_mat_t appB, fmpz_gram_t A, int a, int zeros, int kappamax, int n, mpf_t tmp, mpf_t rtmp, mp_bitcnt_t prec, const fmpz_lll_t fl)¶ This function is like the
mpf
version offmpz_lll_check_babai_heuristic_d()
. However, it also inherits some temporarympf_t
variablestmp
andrtmp
.
-
int
fmpz_lll_advance_check_babai
(int cur_kappa, int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s, d_mat_t appB, int *expo, fmpz_gram_t A, int a, int zeros, int kappamax, int n, const fmpz_lll_t fl)¶ This is a Babai procedure which is used when size reducing a vector beyond an index which LLL has reached.
cur_kappa
is the index behind which we can assumeB
is LLL reduced, whilekappa
is the vector to be reduced. This procedure only size reduces thekappa
-th row by vectors uptocur_kappa
, textbf{not}kappa - 1
.
-
int
fmpz_lll_advance_check_babai_heuristic_d
(int cur_kappa, int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s, d_mat_t appB, int *expo, fmpz_gram_t A, int a, int zeros, int kappamax, int n, const fmpz_lll_t fl)¶ Same as
fmpz_lll_advance_check_babai()
but using the heuristic inner product rather than a purely floating point inner product. The heuristic will compute at full precision when there is cancellation.
Shift¶
-
int
fmpz_lll_shift
(const fmpz_mat_t B)¶ Computes the largest number of non-zero entries after the diagonal in
B
.
Varieties of LLL¶
These programs implement ideas from the book chapter citep{Stehle2010}.
-
int
fmpz_lll_d
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl)¶ This is a mildly greedy version of floating point LLL using doubles only. It tries the fast version of the Babai algorithm (
fmpz_lll_check_babai()
). If that fails, then it switches to the heuristic version (fmpz_lll_check_babai_heuristic_d()
) for only one loop and switches right back to the fast version. It reducesB
in place.U
is the matrix used to capture the unimodular transformations if it is not \(NULL\). An exception is raised if \(U != NULL\) and \(U->r != d\), where \(d\) is the lattice dimension.fl
is the context object containing information containing the LLL parameters delta and eta. The function can perform reduction on both the lattice basis as well as its Gram matrix. The type of lattice representation can be specified via the parameterfl->rt
. The type of Gram matrix to be used in computation (approximate or exact) can also be specified through the variablefl->gt
(applies only iffl->rt
== \(Z_BASIS\)).
-
int
fmpz_lll_d_heuristic
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl)¶ This LLL reduces
B
in place using doubles only. It is similar tofmpz_lll_d()
but only uses the heuristic inner products which attempt to detect cancellations.
-
int
fmpz_lll_mpf2
(fmpz_mat_t B, fmpz_mat_t U, mp_bitcnt_t prec, const fmpz_lll_t fl)¶ This is LLL using
mpf
with the given precision,prec
for the underlying GSO. It reducesB
in place like the other LLL functions. The \(mpf2\) in the function name refers to the way thempf_t
’s are initialised.
-
int
fmpz_lll_mpf
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl)¶ A wrapper of
fmpz_lll_mpf2()
. This currently begins with \(prec == D_BITS\), then for the first 20 loops, increases the precision one limb at a time. After 20 loops, it doubles the precision each time. There is a proof that this will eventually work. The return value of this function is 0 if the LLL is successful or -1 if the precision maxes out beforeB
is LLL-reduced.
-
int
fmpz_lll_wrapper
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl)¶ A wrapper of the above procedures. It begins with the greediest version (
fmpz_lll_d()
), then adapts to the version using heuristic inner products only (fmpz_lll_d_heuristic()
) if \(fl->rt == Z_BASIS\) and \(fl->gt == APPROX\), and finally to the mpf version (fmpz_lll_mpf()
) if needed.U
is the matrix used to capture the unimodular transformations if it is not \(NULL\). An exception is raised if \(U != NULL\) and \(U->r != d\), where \(d\) is the lattice dimension.fl
is the context object containing information containing the LLL parameters delta and eta. The function can perform reduction on both the lattice basis as well as its Gram matrix. The type of lattice representation can be specified via the parameterfl->rt
. The type of Gram matrix to be used in computation (approximate or exact) can also be specified through the variablefl->gt
(applies only iffl->rt
== \(Z_BASIS\)).
-
int
fmpz_lll_d_with_removal
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ Same as
fmpz_lll_d()
but with a removal bound,gs_B
. The return value is the new dimension ofB
if removals are desired.
-
int
fmpz_lll_d_heuristic_with_removal
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ Same as
fmpz_lll_d_heuristic()
but with a removal bound,gs_B
. The return value is the new dimension ofB
if removals are desired.
-
int
fmpz_lll_mpf2_with_removal
(fmpz_mat_t B, fmpz_mat_t U, mp_bitcnt_t prec, const fmpz_t gs_B, const fmpz_lll_t fl)¶ Same as
fmpz_lll_mpf2()
but with a removal bound,gs_B
. The return value is the new dimension ofB
if removals are desired.
-
int
fmpz_lll_mpf_with_removal
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ A wrapper of
fmpz_lll_mpf2_with_removal()
. This currently begins with \(prec == D_BITS\), then for the first 20 loops, increases the precision one limb at a time. After 20 loops, it doubles the precision each time. There is a proof that this will eventually work. The return value of this function is the new dimension ofB
if removals are desired or -1 if the precision maxes out beforeB
is LLL-reduced.
-
int
fmpz_lll_wrapper_with_removal
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ A wrapper of the procedures implementing the base case LLL with the addition of the removal boundary. It begins with the greediest version (
fmpz_lll_d_with_removal()
), then adapts to the version using heuristic inner products only (fmpz_lll_d_heuristic_with_removal()
) if \(fl->rt == Z_BASIS\) and \(fl->gt == APPROX\), and finally to the mpf version (fmpz_lll_mpf_with_removal()
) if needed.
-
int
fmpz_lll_d_with_removal_knapsack
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ This is floating point LLL specialized to knapsack-type lattices. It performs early size reductions occasionally which makes things faster in the knapsack case. Otherwise, it is similar to
fmpz_lll_d_with_removal
.
-
int
fmpz_lll_wrapper_with_removal_knapsack
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ A wrapper of the procedures implementing the LLL specialized to knapsack-type lattices. It begins with the greediest version and the engine of this version, (
fmpz_lll_d_with_removal_knapsack()
), then adapts to the version using heuristic inner products only (fmpz_lll_d_heuristic_with_removal()
) if \(fl->rt == Z_BASIS\) and \(fl->gt == APPROX\), and finally to the mpf version (fmpz_lll_mpf_with_removal()
) if needed.
ULLL¶
-
int
fmpz_lll_with_removal_ulll
(fmpz_mat_t FM, fmpz_mat_t UM, slong new_size, const fmpz_t gs_B, const fmpz_lll_t fl)¶ ULLL is a new style of LLL which does adjoins an identity matrix to the input lattice
FM
, then scales the lattice down tonew_size
bits and reduces this augmented lattice. This tends to be more stable numerically than traditional LLL which means higher dimensions can be attacked using doubles. In each iteration a new identity matrix is adjoined to the truncated lattice.UM
is used to capture the unimodular transformations, whilegs_B
andfl
have the same role as in the previous routines. The function is optimised for factoring polynomials.
LLL-reducedness¶
These programs implement ideas from the paper citep{Villard2007}.
-
int
fmpz_lll_is_reduced_d
(const fmpz_mat_t B, const fmpz_lll_t fl)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
), and otherwise returns zero. The function is mainly intended to be used for testing purposes. It will not always work, but if it does the result is guaranteed.Uses the algorithm of Villard (see url{http://arxiv.org/abs/cs/0701183}).
-
int
fmpz_lll_is_reduced_mpfr
(const fmpz_mat_t B, const fmpz_lll_t fl, mp_bitcnt_t prec)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
), and otherwise returns zero. Thempfr
variables used have their precision set to be exactlyprec
bits. The function is mainly intended to be used for testing purposes. It will not always work, but if it does the result is guaranteed.Uses the algorithm of Villard (see url{http://arxiv.org/abs/cs/0701183}).
-
int
fmpz_lll_is_reduced
(const fmpz_mat_t B, const fmpz_lll_t fl, mp_bitcnt_t prec)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
), and otherwise returns zero. Thempfr
variables used, if any, have their precision set to be exactlyprec
bits. The function is mainly intended to be used for testing purposes. It first tests for LLL reducedness usingfmpz_lll_is_reduced_d()
, followed byfmpz_lll_is_reduced_mpfr()
and finally callsfmpz_mat_is_reduced()
orfmpz_mat_is_reduced_gram()
(depending on the type of input as determined byfl->rt
), if required.
-
int
fmpz_lll_is_reduced_d_with_removal
(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
) and the squared Gram-Schmidt length of each \(i`th vector (where `i\) genewd
) is greater thangs_B
, and otherwise returns zero. The function is mainly intended to be used for testing purposes. It will not always work, but if it does the result is guaranteed.Uses the algorithm of Villard (see url{http://arxiv.org/abs/cs/0701183}).
-
int
fmpz_lll_is_reduced_mpfr_with_removal
(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd, mp_bitcnt_t prec)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
) and the squared Gram-Schmidt length of each \(i`th vector (where `i\) genewd
) is greater thangs_B
, and otherwise returns zero. Thempfr
variables used have their precision set to be exactlyprec
bits. The function is mainly intended to be used for testing purposes. It will not always work, but if it does the result is guaranteed.Uses the algorithm of Villard (see url{http://arxiv.org/abs/cs/0701183}).
-
int
fmpz_lll_is_reduced_with_removal
(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd, mp_bitcnt_t prec)¶ Returns a non-zero value if the matrix
B
is LLL-reduced with factor (fl->delta
,fl->eta
) and the squared Gram-Schmidt length of each \(i`th vector (where `i\) genewd
) is greater thangs_B
, and otherwise returns zero. Thempfr
variables used, if any, have their precision set to be exactlyprec
bits. The function is mainly intended to be used for testing purposes. It first tests for LLL reducedness usingfmpz_lll_is_reduced_d_with_removal()
, followed byfmpz_lll_is_reduced_mpfr_with_removal()
and finally callsfmpz_mat_is_reduced_with_removal()
orfmpz_mat_is_reduced_gram_with_removal()
(depending on the type of input as determined byfl->rt
), if required.
Modified ULLL¶
-
void
fmpz_lll_storjohann_ulll
(fmpz_mat_t FM, slong new_size, const fmpz_lll_t fl)¶ Performs ULLL using
fmpz_mat_lll_storjohann()
as the LLL function.
Main LLL functions¶
-
void
fmpz_lll
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl)¶ Reduces
B
in place according to the parameters specified by the LLL context objectfl
.This is the main LLL function which should be called by the user. It currently calls the ULLL algorithm (without removals). The ULLL function in turn calls a LLL wrapper which tries to choose an optimal LLL algorithm, starting with a version using just doubles (ULLL tries to maximise usage of this), then a heuristic LLL a full precision floating point LLL if required.
U
is the matrix used to capture the unimodular transformations if it is not \(NULL\). An exception is raised if \(U != NULL\) and \(U->r != d\), where \(d\) is the lattice dimension.fl
is the context object containing information containing the LLL parameters delta and eta. The function can perform reduction on both the lattice basis as well as its Gram matrix. The type of lattice representation can be specified via the parameterfl->rt
. The type of Gram matrix to be used in computation (approximate or exact) can also be specified through the variablefl->gt
(applies only iffl->rt
== \(Z_BASIS\)).
-
int
fmpz_lll_with_removal
(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl)¶ Reduces
B
in place according to the parameters specified by the LLL context objectfl
and removes vectors whose squared Gram-Schmidt length is greater than the boundgs_B
. The return value is the new dimension ofB
to be considered for further computation.This is the main LLL with removals function which should be called by the user. Like
fmpz_lll
it calls ULLL, but it also sets the Gram-Schmidt bound to that supplied and does removals.