LLL Algorithm
El algoritmo LLL reduce una base de retículo a una casi ortogonal en tiempo polinómico; su primer vector es a lo sumo 2^((n-1)/2) veces el vector más corto.
Propósito
Realizar reducción aproximada de retículos en tiempo polinómico, ampliamente usada en criptoanálisis y teoría de números.
Mecanismo
Tras la ortogonalización de Gram-Schmidt, comprueba la condición de Lovász (|μ_{i,i-1}|≤1/2 y B_i≥(3/4-μ^2)B_{i-1}), intercambiando y reduciendo cuando falla. El primer vector de la base resultante tiene longitud ≤2^((n-1)/2) * λ_1.
Casos de uso
- Criptoanálisis de retículos
- Factorización de polinomios
- Aproximación al CVP