LLL Algorithm
L'algorithme LLL réduit une base de réseau en une base quasi orthogonale en temps polynomial ; son premier vecteur est au plus 2^((n-1)/2) fois le vecteur le plus court.
Objectif
Effectuer une réduction de réseau approchée en temps polynomial, largement utilisée en cryptanalyse et en théorie des nombres.
Mécanisme
Après orthogonalisation de Gram-Schmidt, il vérifie la condition de Lovász (|μ_{i,i-1}|≤1/2 et B_i≥(3/4-μ^2)B_{i-1}), en échangeant et réduisant lorsqu'elle échoue. Le premier vecteur de la base produite a une longueur ≤2^((n-1)/2) * λ_1.
Cas d’usage
- Cryptanalyse sur réseaux
- Factorisation de polynômes
- Approximation du CVP