Un réseau est un Z-module discret de R
. Réduire un
réseau, c'est trouver une bonne base du réseau,
formée de vecteurs assez courts et assez orthogonaux. C'est un
problème
largement étudié mais
les solutions classiques
- sauf en petite dimension- ne sont jamais constructives.
Lenstra, Lenstra, Lovasz, en 1983, ont
obtenu un algorithme polynomial, appelé LLL,
qui trouve une assez bonne base du réseau. En particulier, le
premier vecteur de cette base est suffisamment court pour jouer le
même
rôle que le plus court vecteur du réseau.
L'algorithme LLL, qui utilise l'arithmétique rationnelle pour manipuler de très grands nombres est extrêmement inefficace. Les implantations pratiques qui tournent (par exemple aux Belle Labs, à l'Université de Francfort et au LIENS) substituent à l'arithmétique rationnelle l'arithmétique flottante de la machine. L'analyse théorique qui justifie et contrôle cette substitution est très délicate et a été principalement menée par C. Schnorr. Le GRECC s'est attaché à concevoir un algorithme parallèle de reduction de réseau qui intègre les méthodes numériques de Schorr. Une solution élégante a ainsi pu être proposée ([Jou93b,Jou93a]), qui est l'un des résultats d'une thèse soutenue récemment.
Le groupe a également utilisé l'algorithme LLL pour calculer explicitement des objets mathématiques complexes: les revêtements de la sphère ramifiés au dessus de trois points seulement. L'étude de ces objets remonte au siècle dernier mais ils ont été remis au goût du jour par ``l'esquisse d'un programme'' rédigée il y a quelques années par Alexandre Grothendieck. Au cours de ce travail, ont été obtenus des résultats sur les propriétés de rationalité de ces revêtements ([Cou93]).