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,\dots ,{𝐛}_d\}$ con coordenadas enteras n-dimensionales , de un retículo L en Rⁿ con $d\le 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

$𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_n\},$

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

${𝐁}^{*}=\{{𝐛}_1^{*},{𝐛}_2^{*},\dots ,{𝐛}_n^{*}\},$

y los coeficientes de Gram-Schmidt

${\mu }_{i,j}=\frac{⟨{𝐛}_i,{𝐛}_j^{*}⟩}{⟨{𝐛}_j^{*},{𝐛}_j^{*}⟩}$, para cada $1\le j<i\le 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:

1. (Tamaño reducido) Para $1\le j<i\le n:\left|{\mu }_{i,j}\right|\le 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 $:\delta \Vert {𝐛}_{k-1}^{*}{\Vert }^2\le \Vert {𝐛}_k^{*}{\Vert }^2+{\mu }_{k,k-1}^2\Vert {𝐛}_{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.

Véase también

• Método de Coppersmith

Bibliografía

• Plantilla:Cita publicación
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita publicación