Algorithme LLL

L'algorithme LLL, des initiales de A. Lenstra, H. Lenstra (en) et L. Lovász, est un algorithme de réduction de réseau qui s'exécute en temps polynomial (cf. théorie de la complexité). L'algorithme LLL prend en entrée un nombre d de vecteurs de base d'un réseau, tels que ces vecteurs sont de dimension n et de norme inférieure à B. L'algorithme retourne en sortie une base de réseau LLL-réduite, c'est-à-dire presque orthogonale, en temps

O(d^5n\log^3 B)\,.

À l'origine, les applications consistaient en la production d'un algorithme de factorisation des polynômes à coefficients rationnels en produits de polynômes irréductibles, ainsi qu'en la résolution des problèmes d'optimisation linéaire avec solutions entières et dimensions fixes. D'autres applications ont été découvertes, notamment en cryptographie à clé publique, par exemple avec RSA, les cryptosystèmes basés sur le problème du sac à dos et NTRUEncrypt.

Références

  • (en) Peter Borwein (en), Computational Excursions in Analysis and Number Theory, Springer, 2002 (ISBN 978-0-387-95444-8) : contient une description complète de l'algorithmes ainsi que des implémentations en pseudocode

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme LLL de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • LLL — Algorithme LLL L algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau qui s exécute en temps polynomial (cf. théorie de la complexité). L algorithme LLL prend en entrée un nombre d de… …   Wikipédia en Français

  • Algorithme de van Hoeij — En mathématiques et en algorithmique, les algorithmes de van Hoeij sont des algorithmes efficaces de factorisation des polynômes à coefficients rationnels, ou plus généralement à coefficients dans un corps de nombres ou de fonctions. Ils datent… …   Wikipédia en Français

  • Réseau (groupe) — Réseau (géométrie) Pour les articles homonymes, voir Réseau. Un réseau est un ensemble discret de points qui emplissent un e …   Wikipédia en Français

  • Réseau (géométrie) — Pour les articles homonymes, voir Réseau. En mathématiques, un réseau d un espace euclidien est un maillage correspondant à la figure de gauche …   Wikipédia en Français

  • Brigitte Vallée — est une mathématicienne et algorithmicienne française née le 6 juin 1950 à Courbevoie en France. Elle est directrice de recherche au CNRS et travaille au Groupe de recherche en informatique, image, automatique et instrumentation de Caen …   Wikipédia en Français

  • Arjen K. Lenstra — Arjen Lenstra Arjen Lenstra à l EPFL en avril 2006 Arjen K. Lenstra est un cryptologue néerlandais né en 1956. Après un doctorat en informatique et en mathématiques, il part aux États Unis en 1984 pour enseigner à l Université de Chicago. Durant… …   Wikipédia en Français

  • Arjen Lenstra — à l EPFL en avril 2006 Arjen K. Lenstra est un cryptologue néerlandais né en 1956. Après un doctorat en informatique et en mathématiques, il part aux États Unis en 1984 pour enseigner à l Université de Chicago. Durant les années 1990, avec son… …   Wikipédia en Français

  • Laszlo Lovasz — László Lovász László Lovász László Lovász (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes . Somm …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

  • 3,14 — Pi Pour les articles homonymes, voir Pi (homonymie) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”