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 𝐁={𝐛1,𝐛2,…,𝐛d} con coordenadas enteras n-dimensionales , de un retículo L en Rn con  d≤n, el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo

O(d5nlog3B)

donde B es la longitud más larga de los bi 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

𝐁={𝐛1,𝐛2,…,𝐛n},

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

𝐁∗={𝐛1∗,𝐛2∗,…,𝐛n∗},

y los coeficientes de Gram-Schmidt

μi,j=⟨𝐛i,𝐛j∗⟩⟨𝐛j∗,𝐛j∗⟩, para cada 1≤j<i≤n.

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

  1. (Tamaño reducido) Para 1≤j<i≤n:|μi,j|≤0.5. Por definición, esta propiedad garantiza la reducción de la longitud de la base.
  2. (Condición de Lovász) Para k = 2,3,..,n :δ‖𝐛k−1∗‖2≤‖𝐛k∗‖2+μk,k−12‖𝐛k−1∗‖2.

Llegados a este punto, estimando el valor del parámetroδ, podemos concluir cómo de bien se reduce la base. A mayores valores de δ mayores reducciones de la base. Inicialmente, A. Lenstra, H. Lenstra and L. Lovász demostraron el algoritmo de simplificación LLL algoritmo para δ=34. Nótese que si bien el algoritmo de simplificación LLL está bien definido para δ=1, la complejidad de tiempo polinomial está garantizada solo para δ∈(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 ci>1 tal que el primer vector de la base no es más de c1 veces más largo que el vector más corto del retículo, el segundo vector de la base es igualmente c2 más largo como máximo que el segundo vector más corto, y así sucesivamente.

Implementaciones en lenguajes computacionales

LLL está implementado en

Véase también