Napias, Huguette
A generalization of the LLL-algorithm over euclidean rings or orders
Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2 , p. 387-396
Zbl 0876.11058 | MR 1438477 | 1 citation dans Numdam
URL stable : http://www.numdam.org/item?id=JTNB_1996__8_2_387_0

De nombreux réseaux célèbres (D 4 ,E 8 , le réseau K 12 de Coxeter-Todd, le réseau Λ 16 de Barnes-Wall, le réseau Λ 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.
Numerous important lattices (D 4 ,E 8 , the Coxeter-Todd lattice K 12 , the Barnes-Wall lattice Λ 16 , the Leech lattice Λ 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.

Bibliographie

[1] Ch. Bachoc, Voisinage au sens de Kneser pour les réseaux quaternioniens, Comm. Math. Helvet. 70 (1995), 350-374. MR 1340098 | Zbl 0843.11022

[2] Ch. Bachoc, Applications of coding theory to the construction of modular lattices, to appear. MR 1439633

[3] Ch. Batut, D. Bernardi, H. Cohen and M. Olivier, User's Guide to PARI-GP.

[4] J.W.S. Cassels, Rational Quadratic Forms, Academic Press, London, 1978. MR 522835 | Zbl 0395.10029

[5] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Graduate Texts in Mathematics, n°138, 1995. MR 1228206 | Zbl 0786.11071

[6] C. Fieker and M.E. Pohst, On lattices over number fields, preprint. MR 1446505

[7] G.H. Hardy and E.M. Wright, An introduction to the theory of numbers (1954), Oxford university press. MR 67125 | Zbl 0058.03301

[8] F. Lemmermeyer, The Euclidean algorithm in algebraic number fields, preprint. MR 1362867

[9] A.K. Lenstra, H.W. Lenstra, Jr and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 682664 | Zbl 0488.12001

[10] J. Martinet, Les réseaux parfaits des espaces euclidiens, to appear. MR 1434803

[11] J. Martinet, Structures algébriques sur les réseaux, Number Theory, S. David éd. (Séminaire de Théorie des Nombres de Paris, 1992 - 93), Cambridge University Press, Cambridge, 1995, pp. 167-186. MR 1345179 | Zbl 0829.11035

[12] H. Napias, Etude expérimentale et algorithmique de réseaux euclidiens, Thèse, Univ. Bordeaux I (1996).

[13] G. Nebe, W. Plesken, Memoirs A.M.S., vol. 116, number 556, pp. 1-144. MR 1265024

[14] M. Pohst, A modification of the LLL-algorithm, J. Symb. Comp. 4 (1987), 123-128. MR 908420 | Zbl 0629.10001