# Lattice reduction

## Overview

Having introduced the LLL reduction, we now provide a more general notions of a reduced basis for a lattice as well as provide bounds for the basis vectors. The key idea behind introducing these definitions is that once we know some basis vector is \[]-reduced, we can bound the sizes of the basis, which is important when algorithms require short vectors in a lattice. For fast algorithms, LLL-reduction is typically the most important notion as it can be computed quickly. Two main definitions appear often when discussing lattice reductions, which we will provide here.

## Definitions

A basis$$\left{b\_i\right}*{i=1}^d$$is **size-reduced** if $$\left|\mu*{i,j}\right|\leq\frac12$$. Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let $$L$$be a lattice, $$1\leq i\leq\dim L=d$$, we define the $$i^\text{th}$$**successive minima**$$\lambda\_i(L)$$ as

$$
\lambda\_i(L)=\min\left(\max\_{1\leq j\leq i}\left(\left\lVert v\_j\right\rVert\right):v\_j\in L\text{ are linearly independent}\right)
$$

Intuitively, $$\lambda\_i(L)$$is the length of the "$$i^\text{th}$$ shortest lattice vector". This intuition is illustrated by the definition of $$\lambda\_1$$:

$$
\lambda\_1(L)=\min\left(\left\lVert v\right\rVert:v\in L\right)
$$

However this is not precise as if $$v$$is the shortest lattice vector, then $$-v$$is also the shortest lattice vector.

Unfortunately, a basis$$b\_i$$for $$L$$where $$\lambda\_i(L)=\left\lVert b\_i\right\rVert$$for dimensions $$5$$ and above. This tells us that we can't actually define "the most reduced basis" in contrast to the 2D case (see [Lagrange's algorithm](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction)) and we would need some other definition to convey this intuition.

An alternate definition of$$\lambda\_i(L)$$that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at least$$i$$linearly independent vectors in$$L$$.

## Exercises

1\) Show that both definitions of $$\lambda\_i$$ are equivalent

2\) Consider the lattice $$L=\begin{pmatrix}2&0&0&0&0\0&2&0&0&0\0&0&2&0&0\0&0&0&2&0\1&1&1&1&1\end{pmatrix}$$. Show that the successive minima are all$$2$$but no basis$$b\_i$$can satisfy $$\left\lVert b\_i\right\rVert=\lambda\_i$$.