# The Basic Concepts of LLL

**In order to read this article properly, you need to have knowledge of linear algebra.**

I’ll not discuss LLL deeply. No proof. No code. Just concepts.

## Introduction

A lattice \(\Lambda\) is a discrete subgroup generated by all the **integer** combinations of the vectors of some basis \(\bf{B}\).

Actually, a lattice can be represented with the matrix of its basis. It has a determinant, like matrix.

The determinant of a lattice \(\Lambda\) (\(\det \Lambda\)) is an important numerical invariant of \(\Lambda\).

If rank of lattice is not full, det 𝛬 is quite complicated but we will discuss only the full rank lattice.

\[\det \Lambda=|\det [\bf{b_1b_2...b_n}]|\]**Hadamard’s inequality** : The determinant is less than or equal to the product of the norm of the basis vectors.

Equality holds if and only if the vectors \(b_i\) are pairwise orthogonal.

### Shortest vector problem

The shortest vector is the following : given a lattice \(\Lambda\) find a shortest vector \(\bf{v}\) among the set of vectors going from the zero element to any non-zero element \(x\) in \(\Lambda\).

The main theoretical result about this is the Minkowski’s theorem which gives us an upper bound for the shortest vector.

**Minkowski’s theorem** : Given a lattice \(\Lambda\) of rank \(m\), if \(\lambda\) is the norm of the shortest vector then,

where \(\frac{m}{2}!\) is inductively defined by \(0!=1,\frac{1}{2}!=\frac{\sqrt{\pi}}{2}\), and \(\frac{n}{2}!=\frac{n}{2}\cdot \frac{n-2}{2}!\)

## LLL Basis reduction

The idea of the basis reduction is to change a basis \(\bf{B}\) of a lattice \(\Lambda\) into a shorter basis \(\bf{B}'\) such that \(\Lambda\) remains the same.

Basis reduction of rank 2 lattices is very easy. Just gram-schmidt and make orthogonal basis.

The LLL-reduction algorithm is a polynomial time lattice reduction algorithm. LLL is used to get an approximation of the shortest vector.

**c-Reduced basis** : A basis \(\{\bf{b_1, b_2, ...,b_m}\}\) is said to be *c-reduced* if and only if its orthogonal basis \(\{\bf{b_1^\ast, b_2^\ast, ...,b_m^\ast}\}\) verifies the following inequality for \(i=1\) to \(m-1\) :

**Theorem 1** : Given a lattice \(\Lambda\) and its *c-reduced* basis \(\{\bf{b_1, b_2, ...,b_m}\}\) with \(c\geq\frac{4}{3}\), then it is near-orthogonal in the sense that:

**Theorem 2** : If the basis \(\{\bf{b_1, b_2, ...,b_m}\}\) is *c-reduced* and \(\lambda\) is the shortest vector norm, then :

**Theorem 3** : For \(c\gt \frac{4}{3}\), LLL finds a *c-reduced* basis in polynomial time.

**Conclusion : So we can make reduced basis by LLL efficiently!**

### References

Factoring Polynomials with Rational Coefficients - A. K. Lenstra

LLL lattice basis reduction algorithm - Helfer Etienne