LLLreduced

LLLreduced refers to a basis of a lattice that has been transformed by the LLL (Lenstra–Lenstra–Lovász) lattice reduction algorithm to satisfy the LLL reduction criteria. A lattice basis B = [b1, ..., bn] in R^m is LLL-reduced when it meets two conditions with a chosen parameter δ in (1/4, 1], typically around 0.75:

- Size reduction: for all i > j, the Gram-Schmidt coefficients μ_{i,j} are small in absolute value (often |μ_{i,j}| ≤ 1/2). This keeps the basis vectors nearly orthogonal in the Gram-Schmidt sense.

- Lovász condition: for the Gram-Schmidt vectors b_i^*, the inequality δ ||b_i^*||^2 ≤ ||b_{i+1}^*||^2 holds for all i.

Here μ_{i,j} are the coefficients from the Gram-Schmidt process and b_i^* are the orthogonalized basis vectors. An LLL-reduced basis is not necessarily the shortest possible basis, but it is relatively short and well-conditioned, with the first vector length bounded in terms of the lattice's shortest nonzero vector λ1 (for example, ∥b1∥ ≤ 2^{(n−1)/2} λ1 in the standard bound).

LLL reduction is achieved by the LLL algorithm, which runs in polynomial time in the dimension and the size of the input. In practice, LLL-reduced bases are used in number theory, computational algebra, and cryptography to obtain short, nearly orthogonal vectors, to solve approximate shortest vector problems, and as a preprocessing step for more intensive lattice reduction or cryptanalytic tasks.