Tout le monde connaît l'algorithme d'Euclide, qui permet de calculer efficacement le plus grand commun diviseur de deux entiers naturels. Ce que l'on sait moins, c'est que Gauss a découvert au dix-neuvième siècle une extension élégante de cet algorithme dans le plan, qui résout un cas particulier de ce que l'on appelle aujourd'hui le problème du plus court vecteur. Ce problème consiste en général à trouver un plus court vecteur non nul dans un réseau à n dimensions : les réseaux sont des analogues discrets des espaces euclidiens ; ce sont des "déformations" de l'ensemble des vecteurs à n coordonnées entières.
Malheureusement, le problème du court vecteur devient de plus en plus dur à mesure que la dimension n augmente. Il y a cinq ans, il a été démontré que ce problème était "NP-dur" : les meilleurs algorithmes connus et prouvés pour résoudre ce problème ont un temps de calcul exponentiels en n. Ce problème est d'ailleurs utilisé depuis peu en cryptographie : une start-up américaine (NTRU) a développé un système de chiffrement très performant dont la sécurité repose sur la difficulté du problème du court vecteur dans certains types de réseaux.
Cet exposé se veut une initiation à l'algorithmique des réseaux, c'est-à-dire à la géométrie des nombres algorithmique.