Lattice reduction (LLL)

A lattice is a discrete subgroup L = \mathbb{Z} b_1 + \cdots + \mathbb{Z} b_d of \mathbb{R}^n generated by linearly independent vectors b_1, \ldots, b_d, its basis. Lattice reduction transforms a basis into one whose vectors are short and nearly orthogonal. The LLL algorithm of Lenstra, Lenstra and Lovász [LLL1982] does this in polynomial time, and its output is good enough for factoring polynomials over \mathbb{Q} [LLL1982; vHo2002], finding integer relations and minimal polynomials of algebraic numbers, simultaneous Diophantine approximation, and many problems in cryptanalysis. FLINT implements LLL for integer lattices, given by a basis (the rows of an fmpz_mat_t) or by a Gram matrix. There is no generic gr_mat version of the reduction itself; gr_mat provides the reducedness test gr_mat_is_row_lll_reduced_naive, which fmpz_mat_is_reduced uses.

LLL-reduced bases#

Let b_1^*, \ldots, b_d^* be the Gram–Schmidt orthogonalisation of the basis: b_i^* = b_i - \sum_{j < i} \mu_{ij} b_j^* with \mu_{ij} = \langle b_i, b_j^* \rangle / r_{jj} and r_{jj} = \lVert b_j^* \rVert^2. Write r_{ij} = \mu_{ij} r_{jj} = \langle b_i, b_j^* \rangle.

The original definition has \eta = \frac12; the relaxation \eta > \frac12 is needed when the Gram–Schmidt data are only known approximately [NS2009]. FLINT's default parameters are \delta = 0.99 and \eta = 0.51.

The LLL algorithm#

With exact rational arithmetic, as in fmpz_mat_lll_original, the Gram–Schmidt data have O(d \log B) bits and the algorithm costs O(d^5 n \log^3 B) bit operations with classical arithmetic [LLL1982]. fmpz_mat_lll_storjohann follows Storjohann's modified LLL [Sto1996]. It works with the integral quantities D_j \mu_{ij} and D_j, where D_j = \prod_{l \le j} r_{ll} are the leading principal minors of the Gram matrix, all obtained by fraction-free elimination of the Gram matrix (Fraction-free elimination), and improves the dependence of the cost on the dimension.

Floating-point LLL: the L² algorithm#

The Gram–Schmidt data need not be exact: it suffices to know them well enough to decide the size reductions and Lovász' conditions. Schnorr and Euchner [SE1994] introduced floating-point LLL; Nguyen and Stehlé [NS2005; NS2009] gave the first provable variant, L², whose bit complexity is quadratic in \log B, by computing the Gram–Schmidt coefficients from the exact Gram matrix entries \langle b_i, b_j \rangle with a Cholesky-like recurrence in floating point:

and by using lazy size reduction: the size reduction of b_k is repeated, recomputing r_{kj} and \mu_{kj} from the updated Gram entries, until all |\mu_{kj}| \le \bar\eta for a slightly smaller \bar\eta. They prove that a precision of d \log_2 \frac{(1 + \eta)^2} {\delta - \eta^2} + o(d) bits, that is about 1.6 d bits for parameters close to (1, \frac12), suffices. This is fmpz_lll's algorithm; see also the survey [Stehle2010] and the implementation notes in [Ste2005].

The test with \bar\delta > \delta and \bar\eta < \eta leaves a margin for the rounding errors, so that the output is (\delta, \eta)-reduced when the precision is sufficient. If the Babai step does not make progress, that is, if after 20 iterations the largest exponent of the \mu_{\kappa j} fails to decrease by 5, the precision is deemed insufficient and the function returns -1.

Precision strategies#

fmpz_lll implements the L² loop with three kinds of arithmetic and moves to the next one when the previous one fails or does not produce a reduced basis:

• fmpz_lll_d works in double. Each basis vector is approximated by a vector of doubles scaled by a power of two (_fmpz_vec_get_d_vec_2exp), so that the exponent range of doubles is not a limitation, and the Gram matrix entries are computed from these approximations (gram type APPROX) or kept exactly as fmpz (gram type EXACT). After 50 failures of the fast Babai step it switches to the heuristic one for one iteration.
• fmpz_lll_d_heuristic computes the approximate dot products with fmpz_lll_heuristic_dot, which detects cancellation (a result much smaller than the product of the norms) and then recomputes the dot product exactly from the integer vectors, an idea from fplll [Ste2005; Stehle2010].
• fmpz_lll_mpf2 works with floating-point numbers of a given precision, using nfloat when the precision allows it and arf otherwise; when the entries are small, the Gram entries are computed exactly from a packed copy of the basis and then rounded. fmpz_lll_mpf calls it with precisions 64, 128, \ldots, 1280 bits and then doubles, until the result is reduced.

fmpz_lll_wrapper runs fmpz_lll_d; if it fails or the result is not certified reduced, fmpz_lll_d_heuristic (for bases with approximate Gram matrix); and finally fmpz_lll_mpf. For a basis given by its Gram matrix, or with an exact Gram matrix, it goes directly from fmpz_lll_d to fmpz_lll_mpf.

Packed bases#

When the entries are small, the floating-point variants keep the basis in a packed form (fmpz_lll_packed_t): every entry occupies the same number of limbs in two's complement, and the rows are contiguous. Row operations b_k \gets b_k - x b_j are then done limb-wise modulo a power of two, which is exact because every row carries an upper bound on the bit length of its entries that all operations maintain; the number of limbs per entry grows and shrinks as needed. This is much cheaper than operating on fmpz entries, and the dot products for exact Gram entries use fixed-size kernels.

Certified reducedness#

After the floating-point algorithm, fmpz_lll_is_reduced checks that the output really is reduced. fmpz_lll_is_reduced_d follows Villard [Villard2007]: it computes an approximate QR factorisation A \approx QR of the basis in double precision, an approximate inverse V \approx R^{-1}, and with directed rounding (fesetround) rigorous enclosures of RV - I and of the backward error, from which it derives intervals containing the true Gram–Schmidt quantities and checks the LLL conditions on them. fmpz_lll_is_reduced_mpfr does the same with nfloat numbers of the given precision and directed rounding. Both are one-sided: a return value of 1 is a proof, 0 is inconclusive. fmpz_lll_is_reduced falls back to the exact tests fmpz_mat_is_reduced (ball arithmetic, then rational arithmetic) and fmpz_mat_is_reduced_gram.

Removals#

In van Hoeij's factoring algorithm [vHo2002; vHN2010], only the lattice vectors of norm at most a bound are of interest, and vectors with large Gram–Schmidt norm at the end of a reduced basis can be discarded. The functions with removal take a bound gs_B and return the number newd of vectors to keep: after the reduction, the last vectors whose squared Gram–Schmidt norm exceeds the bound (by a factor 2 in the floating-point estimate) are dropped from the count, and the first newd vectors are (\delta, \eta)-reduced. A vector of a reduced basis whose Gram–Schmidt norm exceeds the bound cannot contribute to a vector of norm at most the bound with the following vectors. During the reduction, the dimension is decreased as soon as the last vector is estimated to exceed the bound. The knapsack variant fmpz_lll_d_with_removal_knapsack additionally size-reduces each new vector in advance the first time it is reached, which pays off for the knapsack-type lattices of factoring.

Truncation: ULLL#

The cost of floating-point LLL grows with the size of the entries, while the transformation found by reducing a truncated basis, with only the leading s bits of each entry, often does most of the work. fmpz_lll uses this strategy, called ULLL in FLINT and developed by Novocin and van Hoeij [Nov2008; vHN2010] for factoring:

Since each pass only applies unimodular transformations, the lattice is unchanged and the final pass guarantees reducedness; the truncated passes work with entries of s + O(d) bits, mostly in doubles. For Gram matrix input there is no truncation. fmpz_lll_storjohann_ulll is the same strategy with fmpz_mat_lll_storjohann.

Use in FLINT#

Asymptotically faster algorithms, such as the quasi-linear time algorithm of Novocin, Stehlé and Villard [NSV2011], are not implemented.