## [Algorithme LLL](/fr/node/63531) Définition Un algorithme de réduction de réseau en temps polynomial qui, pour une base d'un réseau euclidien, renvoie une base réduite dont les vecteurs sont relativement courts et presque orthogonaux selon la condition de Lovász ; utilisé en théorie algorithmique des nombres, en algèbre et en cryptanalyse. ## Principe Principe S'appuie sur l'orthogonalisation de Gram–Schmidt et des opérations locales de réduction de taille guidées par l'inégalité de Lovász pour remplacer itérativement des vecteurs de base par des combinaisons linéaires plus courtes jusqu'à obtenir une base réduite. ## Démonstration Démonstration À partir d'un réseau entier engendré par les lignes d'une matrice, appliquer les opérations d'échange et de réduction de taille de LLL produit une base contenant souvent un vecteur court exploitable pour le factorisation de polynômes sur Q ou l'attaque d'instances de type sac à dos. ## Mauvaise application Mauvaise application Utiliser LLL comme solveur déterministe du vecteur le plus court : considérer sa sortie comme le véritable vecteur le plus court sans reconnaître que LLL ne garantit qu'une approximation conduit à des affirmations erronées sur la sécurité ou les résultats algorithmiques. ## Conséquence Conséquence Une utilisation correcte fournit une base approximativement réduite calculable efficacement, permettant de résoudre en pratique la reconstruction rationnelle, la factorisation de polynômes, l'approximation diophantienne et la compromission de cryptosystèmes à réseau faibles. ## Inversion Inversion La notion inverse consiste à accepter des bases de réseau arbitraires non réduites : des bases longues et fortement biaisées masquent les vecteurs courts et rendent les calculs ultérieurs inefficaces ou numériquement instables. ## Limite Limite S'applique aux réseaux euclidiens sur Z ou Q de dimension modérée ; exclut les garanties exactes pour le vecteur le plus court ou les réseaux de très haute dimension où le facteur d'approximation devient important et où d'autres algorithmes (BKZ, solveurs SVP exacts) sont requis. ## Tension sémantique Tension sémantique LLL est souvent confondu avec des algorithmes exacts de vecteur le plus court ou avec des heuristiques de tamisage de réseaux ; la tension porte sur l'approximation pratique, les bornes prouvables en temps polynomial et la recherche d'une meilleure qualité de réduction. ## Synthèse Synthèse L'Algorithme LLL est une procédure en temps polynomial qui utilise des projections de Gram–Schmidt et des étapes locales de réduction selon Lovász pour transformer une base de réseau en une base réduite et utile en pratique, constituée de vecteurs relativement courts et presque orthogonaux.