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ⁿ 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:

1. (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.
2. (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.

Véase también

• Método de Coppersmith

Bibliografía

• Napias, Huguette (1996). «A generalizaion of the LLL algorithm over euclidean rings or orders». J. The. Nombr. Bordeaux 8 (2): 387-396. 
• Cohen, Henri (2000). A course in computational algebraic number theory. GTM 138. Springer. ISBN 3-540-55640-0. 
• Borwein, Peter (2002). Computational Excursions in Analysis and Number Theory. ISBN 0-387-95444-9. 
• Luk, Franklin T.; Qiao, Sanzheng (2011). «A pivoted LLL algorithm». Lin. Alg. Appl. 434: 2296-2307. doi:10.1016/j.laa.2010.04.003. 

• Datos: Q1683648