Une approche géométrique de la réduction des réseaux en petite dimension. (A geometric approach to lattice reduction in small dimension). (French) Zbl 0602.10022

Vallée, Brigitte

Université de Caen. 166 p. (1986).

Ce travail est une étude algorithmique de la réduction des réseaux et des formes quadratiques définies positives. Après avoir rappelé les liens entre ces deux théories, nous en énonçons les principaux résultats connus, en insistant sur le fait que les solutions classiques ne sont presque jamais constructives, sauf en petites dimensions \((n=2,3)\). En chacune de ces dimensions, il existe un algorithme de réduction, dû à Gauss: complète réduction en dimension 2, pseudo-réduction en dimension 3.
En dimension 2, nous introduisons alors une transcription ’affine’ de cet algorithme, qui nous permet d’en exhiber le plus mauvais cas et de résoudre le problème non homogène associé.
En dimension 3, nous généralisons ce point de vue, et nous obtenons un algorithme de ’complète’ réduction, qui travaille en temps polynomial, et qui construit une base minimale du réseau: nous pouvons réduire ainsi complètement les formes quadratique entières ternaires et résoudre aussi le problème non homogène associé.
Replaçant aussi ce travail dans un cadre plus général, nous montrons que l’algorithme L3 coïncide avec l’algorithme de pseudo- réduction de Gauss en dimension 3 et qu’il le généralise en toute dimension. Nous construisons aussi, en dimension quelconque, un algorithme qui permet de résoudre, en temps polynomial quand la dimension est fixée, le problème de la recherche du point d’un réseau le plus proche d’un point donné de l’espace.
En conclusion, nous présentons une annexe de programmation des deux algorithmes de la dimension 3, afin de comparer de manière expérimentale leur complexité et leur configuration de sortie.

MSC:

11H55	Quadratic forms (reduction theory, extreme forms, etc.)
68Q25	Analysis of algorithms and problem complexity
90C10	Integer programming
11-04	Software, source code, etc. for problems pertaining to number theory
11H06	Lattices and convex bodies (number-theoretic aspects)

Keywords:

polynomial complexity; lattice reduction; computational number theory; integer lattices; reduction of quadratic forms; Gauss algorithms; algorithm L3; basis reduction; Minkowski reduction; Hermitian reduction; minimal basis; shortest vector; Voronoi reduction; nearest point; computational complexity