Algoritmo LLL
# Algoritmo LLL

El algoritmo de simplificación de bases de retículos de Lenstra–Lenstra–Lovász (LLL) es un algoritmo de simplificación de retículos de complejidad polinomial inventado por Arjen Lenstra, Hendrik Lenstra y László Lovász en 1982. Dada una base $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ con coordenadas enteras n-dimensionales , de un retículo L en $R^n$ con $\ d\leq n$, el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo

    $O(d^{5}n\log ^{3}B)\,$

donde B es la longitud más larga de los $b_{i}$ bajo la norma euclídea.

Las aplicaciones originales eran dar algoritmos de complejidad polinomial para factorizar polinomios que coeficientes racionales, para encontrar aproximaciones racionales simultáneas a los números reales, y para resolver el problema de la programación lineal entera en dimensiones fijadas.

## Simplificación del LLL

La definición exacta de LLL-reducido es la siguiente: Dada una base

    $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},$

se definen su base ortogonal obtenida por el proceso de ortogonalización de Gram-Schmidt

    $\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

y los coeficientes de Gram-Schmidt

    $\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, para cada $1\leq j<i\leq n$.

Entonces la base $B$ es LLL-reducida si existe un parámetro $\delta$ en (0.25,1] tal que se cumplen las siguientes condiciones:

* (Tamaño reducido) Para $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. Por definición, esta propiedad garantiza la reducción de la longitud de la base.
* (Condición de Lovász) Para k = 2,3,..,n $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$.

Llegados a este punto, estimando el valor del parámetro$\delta$, podemos concluir cómo de bien se reduce la base. A mayores valores de $\delta$ mayores reducciones de la base. Inicialmente, A. Lenstra, H. Lenstra and L. Lovász demostraron el algoritmo de simplificación LLL algoritmo para $\delta ={\frac {3}{4}}$. Nótese que si bien el algoritmo de simplificación LLL está bien definido para $\delta =1$, la complejidad de tiempo polinomial está garantizada solo para $\delta \in (0.25,1)$ .

El algoritmo LLL calcula bases LLL-reducidas. No se conoce un algoritmo eficiente que calcule una base cuyos vectores sean tan pequeños como sea posible para retículos de dimensiones mayores que 4. Sin embargo, una base LLL-reducida es casi tan pequeña como sea posible, en le sentido de que hay unas cotas absolutas $c_{i}>1$ tal que el primer vector de la base no es más de $c_{1}$ veces más largo que el vector más corto del retículo, el segundo vector de la base es igualmente $c_{2}$ más largo como máximo que el segundo vector más corto, y así sucesivamente.

## Implementaciones en lenguajes computacionales

LLL está implementado en

* Arageli como la función lll_reduction_int.
* fpLLL como implementación que se ejecuta en local.
* GAP como la función LLLReducedBasis.
* Macaulay2 como la función LLL en el paquete LLLBases.
* Magma como las funciones LLL y LLLGram (tomando una matriz de Gram).
* Maple como la función IntegerRelations[LLL].
* Mathematica como la función LatticeReduce.
* Number Theory Library (NTL) como la función LLL.
* PARI/GP como la función qflll.
* Pymatgen como la función analysis.get_lll_reduced_lattice.
* Sage como el método LLL llevado a cabo por fpLLL y NTL.
