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 ${\displaystyle \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 ${\displaystyle \ d\leq n}$, el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo

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

donde B es la longitud más larga de los ${\displaystyle 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

${\displaystyle \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

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

y los coeficientes de Gram-Schmidt

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

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

1. (Tamaño reducido) Para ${\displaystyle 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 ${\displaystyle \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${\displaystyle \delta }$, podemos concluir cómo de bien se reduce la base. A mayores valores de ${\displaystyle \delta }$ mayores reducciones de la base. Inicialmente, A. Lenstra, H. Lenstra and L. Lovász demostraron el algoritmo de simplificación LLL algoritmo para ${\displaystyle \delta ={\frac {3}{4}}}$. Nótese que si bien el algoritmo de simplificación LLL está bien definido para ${\displaystyle \delta =1}$, la complejidad de tiempo polinomial está garantizada solo para ${\displaystyle \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 ${\displaystyle c_{i}>1}$ tal que el primer vector de la base no es más de ${\displaystyle c_{1}}$ veces más largo que el vector más corto del retículo, el segundo vector de la base es igualmente ${\displaystyle 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.
• 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.

Referencias

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.