Un algoritmo de reducción de redes en tiempo polinómico que, dada una base de una red euclídea, devuelve una base reducida cuyos vectores son relativamente cortos y casi ortogonales según la condición de Lovász; muy usado en teoría de números computacional, álgebra y criptoanálisis.

Principio

Emplea la ortogonalización de Gram–Schmidt y pasos locales de reducción de tamaño guiados por la desigualdad de Lovász para reemplazar iterativamente vectores de la base por combinaciones lineales más cortas hasta alcanzar una base reducida.

Demostración

Dada una red entera generada por las filas de una matriz, aplicar las operaciones de intercambio y reducción de LLL produce una base que con frecuencia contiene un vector corto útil para factorizar polinomios sobre los racionales o atacar instancias tipo mochila.

Aplicación incorrecta

Usar LLL como solucionador determinista del vector más corto: tratar su salida como el verdadero vector más corto sin reconocer que LLL solo garantiza una aproximación puede conducir a afirmaciones incorrectas sobre seguridad o resultados algorítmicos.

Consecuencia

Su uso correcto genera una base aproximada computable eficientemente que permite resolver en la práctica reconstrucción racional, factorización de polinomios, aproximación diofántica y romper criptosistemas débiles basados en redes.

Inversión

La inversión es aceptar bases de red arbitrarias sin reducción: bases largas y muy inclinadas que ocultan vectores cortos y hacen que los cálculos posteriores sean ineficientes o numéricamente inestables.

Límite

Se aplica a redes euclídeas sobre Z o Q con dimensión moderada; excluye garantías exactas para el vector más corto o redes de muy alta dimensión donde el factor de aproximación crece y se requieren otros algoritmos (BKZ, solucionadores SVP exactos).

Tensión semántica

LLL suele confundirse con algoritmos exactos de SVP o con heurísticas de cribado de redes; la tensión está entre la aproximación práctica, las cotas demostrables en tiempo polinómico y la búsqueda de mayor calidad de reducción.

Síntesis

El Algoritmo LLL es un procedimiento en tiempo polinómico que usa proyecciones de Gram–Schmidt y pasos locales de reducción según Lovász para convertir una base de red en una base reducida y útil en la práctica, compuesta por vectores relativamente cortos y casi ortogonales.