LLL reduced

Definition

Let δ(14,1)\delta\in\left(\frac14,1\right). A basis{bi}i=1d\left\{b_i\right\}_{i=1}^dis δ\delta- LLL-reduced if it is size reduced and satisfy the Lovász condition, i.e.

δbi2bi+1+μi+1,ibi2\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2

This notion of reduction is most useful to use for fast algorithms as such a basis can be found in polynomial time (see LLL reduction).

Bounds