Algorithme de réduction de base de réseau en temps polynomial qui, donné une base d'un réseau dans un espace euclidien, renvoie une base réduite composée de vecteurs relativement courts et presque orthogonaux satisfaisant des étapes de size-reduction et la condition de Lovász pour un paramètre choisi δ∈(1/4,1].

Principe

Combiner l'orthogonalisation de Gram–Schmidt avec des étapes de réduction de taille et un critère d'échange (la condition de Lovász) pour améliorer progressivement la qualité de la base ; l'algorithme équilibre temps de calcul et qualité d'approximation via le paramètre δ.

Démonstration

En dimension deux, LLL réduit une base {b1,b2} par réduction de taille pour assurer |μ_{1,2}|≤1/2 puis, si ‖b2*‖^2 + μ_{1,2}^2‖b1*‖^2 < δ‖b1*‖^2 procède à l'échange des vecteurs ; après ces opérations la base de sortie satisfait des bornes prouvables sur les longueurs par rapport au vecteur le plus court du réseau.

Mauvaise application

Considérer LLL comme un solveur exact du problème du plus court vecteur (SVP) ou supposer qu'il brisera la cryptographie basée sur les réseaux en haute dimension sans tenir compte de son facteur d'approximation et de la dégradation exponentielle avec la dimension ; LLL fournit des approximations en temps polynomial, pas des solutions exactes en général.

Conséquence

Produit des bases réduites utilisables pour la détection de relations entières, des algorithmes de factorisation, des heuristiques de cryptanalyse et la théorie algorithmique des nombres ; il donne des approximations en temps polynomial du SVP et facilite des améliorations pratiques dans les calculs sur réseaux.

Inversion

L'inverse serait un agrandissement arbitraire de base : appliquer des transformations unimodulaires qui augmentent les longueurs des vecteurs ou détruisent l'orthogonalité ; des algorithmes exacts comme l'énumération ou l'algorithme de Kannan inversent l'approximation en trouvant des vecteurs exactement plus courts au prix d'un coût exponentiel.

Limite

S'applique aux réseaux euclidiens représentés par des bases finies en dimension fixée ; les garanties de performance et d'approximation se détériorent avec l'accroissement de la dimension et dépendent du choix de δ ; il ne garantit pas les vecteurs les plus courts en haute dimension.

Tension sémantique

Confrontation conceptuelle avec des procédures plus puissantes mais exponentielles comme BKZ ou l'énumération : LLL est polynomial et pratique en dimensions modérées, tandis que BKZ (avec grand bloc) fournit de meilleures approximations à coût computationnel supérieur.

Synthèse

LLL est une méthode pratique de réduction en temps polynomial : en alternant réduction de taille, orthogonalisation de Gram–Schmidt et échanges basés sur la condition de Lovász, elle produit une base avec des bornes d'approximation prouvables, échangeant optimalité contre temps polynomial.