con coordenadas enteras n-dimensionales , de un retículo L en Rn con
, el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo donde B es la longitud más larga de los
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.
en (0.25,1] tal que se cumplen las siguientes condiciones: Llegados a este punto, estimando el valor del parámetro
, podemos concluir cómo de bien se reduce la base.
Nótese que si bien el algoritmo de simplificación LLL está bien definido para
, la complejidad de tiempo polinomial está garantizada solo para
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
veces más largo que el vector más corto del retículo, el segundo vector de la base es igualmente
más largo como máximo que el segundo vector más corto, y así sucesivamente.