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 B = { b 1 , b 2 , … , b d } {\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}} con coordenadas enteras n-dimensionales , de un retículo L en Rn con d ≤ n {\displaystyle \ 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 ) {\displaystyle O(d^{5}n\log ^{3}B)\,} donde B es la longitud más larga de los b i {\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.