> For the complete documentation index, see [llms.txt](https://cryptohack.gitbook.io/cryptobook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/lll-reduced.md).

# LLL reduced

## Definition

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

$$
\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](/cryptobook/lattices/lll-reduction/lll-reduced-basis.md)).

## Bounds

$$
\begin{align\*}
\left\lVert b\_1\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d\\
\left\lVert b\_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}2}\lambda\_i(L)\\
\prod\_{i=1}^d\left\lVert b\_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d(d-1)}4}\text{vol}(L)
\end{align\*}
$$