fmpz_lll.h

Sets fl to the default parameters \delta = 0.99, \eta = 0.51, with representation Z_BASIS and Gram type APPROX.

Sets the fields of fl to the given values. Nothing is checked.

Sets fl to random valid parameters, \delta \in (0.25, 1) and \eta \in (0.5, \sqrt{\delta}), and a random representation and Gram type. For testing.

Reduces B according to fl. For Z_BASIS input the rows of B may be linearly dependent; the zero vectors of the result then come first. See Reducing a lattice basis.

Reduces B like fmpz_lll and returns the number newd of leading vectors to keep: the trailing vectors whose squared Gram–Schmidt norm exceeds the bound gs_B are not counted. If gs_B is NULL, no removal is done and the function returns 0.

L² with Gram–Schmidt data in double precision, the basis vectors being approximated by double vectors scaled by powers of two. Uses the fast Babai procedure (fmpz_lll_check_babai), switching to the heuristic one for one iteration after 50 failures. Fails, returning -1, if the precision is insufficient or an iteration limit is reached.

As fmpz_lll_d, but always computes the approximate dot products with fmpz_lll_heuristic_dot, which recomputes a dot product exactly when it detects cancellation.

As fmpz_lll_d_with_removal, but size-reduces each new vector in advance when it is first reached, which is faster for knapsack-type lattices, and tolerates 150 instead of 50 failures of the fast Babai procedure.

L² with Gram–Schmidt data in floating point of prec bits. Returns -1 if the precision turns out to be insufficient.

Calls fmpz_lll_mpf2 (respectively the version with removal) with precisions 64, 128, 192, \ldots bits for the first 20 attempts and then doubling the precision, until the result is reduced according to fmpz_lll_is_reduced (respectively fmpz_lll_is_reduced_with_removal). Returns the value of the last call. Since a precision linear in the dimension suffices [NS2009], this terminates.

Reduces B with the cheapest strategy that succeeds: fmpz_lll_d (or fmpz_lll_d_with_removal, fmpz_lll_d_with_removal_knapsack); if it fails or the result is not reduced, fmpz_lll_d_heuristic (or its removal version), but only for Z_BASIS input with Gram type APPROX; and finally fmpz_lll_mpf (or fmpz_lll_mpf_with_removal). Returns the value of the last strategy run.

Reduces FM with the truncation strategy: while the entries have more than new_size bits, the lattice (I \mid \lfloor \mathit{FM}/2^e \rfloor), with e chosen to leave new_size bits, is reduced with fmpz_lll_wrapper_with_removal_knapsack and its transformation applied to FM; then FM itself is reduced. Returns the number of vectors kept, as fmpz_lll_with_removal. UM captures the transformation as in the other functions. For GRAM input no truncation is done.

The truncation strategy of fmpz_lll_with_removal_ulll with fmpz_mat_lll_storjohann as the reduction, without removals and without transformation matrix. For GRAM input it calls fmpz_lll_with_removal_ulll without removal bound.

Returns 1 if B is proven to be reduced (in the sense of fmpz_mat_is_reduced, fmpz_mat_is_reduced_gram or their removal versions, according to fl->rt), and 0 if the test is inconclusive. The _d versions work in double arithmetic, the _mpfr versions with nfloat numbers of prec bits; both use directed rounding to obtain rigorous error bounds.

Returns 1 if B is reduced and 0 otherwise, conclusively. Leading zero rows of a basis are ignored. The fast tests fmpz_lll_is_reduced_d and fmpz_lll_is_reduced_mpfr (with precision prec) are tried first; if both are inconclusive, the exact test fmpz_mat_is_reduced (or fmpz_mat_is_reduced_gram, or the removal versions) decides. If gs_B is NULL, fmpz_lll_is_reduced_with_removal is fmpz_lll_is_reduced.

Size reduction in double precision, with plain floating-point dot products, respectively with fmpz_lll_heuristic_dot.

As fmpz_lll_check_babai and fmpz_lll_check_babai_heuristic_d, but reduce row kappa only against the rows before cur_kappa, which are already LLL-reduced. Used for the early size reductions of the knapsack variant.

Size reduction with Gram–Schmidt data in the floating-point type of the context ctx (nfloat or arf), as used by fmpz_lll_mpf2; s is a vector and tmp, rtmp are scratch variables, all of that type.

Returns the dot product of the first len2 entries of the double vectors vec1 and vec2, which approximate rows k and j of B scaled by powers of two. If cancellation is detected (the square of the result is at most 2^{-70} times the product of the squared norms), the dot product of the rows of B is computed exactly instead and returned scaled by 2^{-\mathit{exp\_adj}}, where exp_adj is the sum of the scaling exponents of the two rows.

Returns the largest distance, over the rows i of B, between column i and the last nonzero entry of row i, computed incrementally. The reduction functions only consider the first \min(\mathit{kappamax} + 1 + \mathit{shift}, n) columns when computing dot products, which saves work for bases in triangular form.

Returns the number of limbs per entry for packing B: enough for its largest entry plus 18 bits of headroom.

Initialises P as a packed d \times n matrix with m limbs per entry, respectively frees it.

Packs B, whose entries must fit in m\beta - 2 bits, into P, respectively unpacks P into B (rows in their current order).

Recomputes the exact bit bound of row i; increases the number of limbs per entry by one; decreases it by one if all rows fit comfortably in one limb less.

Moves row i to position j, shifting the rows in between (by permuting row pointers).

Sets row i to row i minus row j, plus row j, minus x times row j, respectively minus x 2^e times row j, exactly, growing the representation if necessary.

Sets appv to double approximations of the entries of row i scaled by 2^{-e} and returns e, as _fmpz_vec_get_d_vec_2exp; also sets the bit bound of the row to its exact value.

Sets res to the exact dot product of the first len entries of rows i and j.

fmpz_lll_heuristic_dot for a packed basis.

The Babai procedures fmpz_lll_check_babai (or fmpz_lll_check_babai_heuristic_d if heuristic is nonzero), fmpz_lll_advance_check_babai and fmpz_lll_check_babai_heuristic operating on a packed basis. In the multiprecision version the Gram matrix entries are computed exactly.