A generalization of the LLL-algorithm over euclidean rings or orders

Napias, Huguette

Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 387-396

Abstract (VO)

Numerous important lattices ($D_4,E_8$, the Coxeter-Todd lattice $K_{12}$, the Barnes-Wall lattice ${\Lambda }_{16}$, the Leech lattice ${\Lambda }_{24}$, as well as the $2$-modular $32$-dimensional lattices found by Quebbemann and Bachoc) possess algebraic structures over various Euclidean rings, e.g. Eisenstein integers or Hurwitz quaternions. One obtains efficient algorithms by performing within this frame the usual reduction procedures, including the well known LLL-algorithm.

Résumé

De nombreux réseaux célèbres ($D_4,E_8$, le réseau $K_{12}$ de Coxeter-Todd, le réseau ${\Lambda }_{16}$ de Barnes-Wall, le réseau ${\Lambda }_{24}$ de Leech, les réseaux $2$-modulaires de dimension 32 de Quebbemann et de Bachoc, ... ) sont munis de structures algébriques sur divers anneaux euclidiens, entiers d’Eisenstein ou quaternions de Hurwitz, par exemple. Les procédés usuels de réduction, et en particulier l’algorithme LLL, deviennent plus performants lorsqu’on les adapte à ces structures.