# 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](/cryptobook/lattices/lll-reduction/gaussian-reduction.md)) 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$$.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.