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

Huguette Napias

Huguette Napias

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

Résumé
Abstract

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.

MR Zbl

@article{JTNB_1996__8_2_387_0,
     author = {Huguette Napias},
     title = {A generalization of the {LLL-algorithm} over euclidean rings or orders},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {387--396},
     publisher = {Universit\'e Bordeaux I},
     volume = {8},
     number = {2},
     year = {1996},
     zbl = {0876.11058},
     mrnumber = {1438477},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_387_0/}
}

TY  - JOUR
AU  - Huguette Napias
TI  - A generalization of the LLL-algorithm over euclidean rings or orders
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1996
SP  - 387
EP  - 396
VL  - 8
IS  - 2
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_387_0/
LA  - en
ID  - JTNB_1996__8_2_387_0
ER  -

%0 Journal Article
%A Huguette Napias
%T A generalization of the LLL-algorithm over euclidean rings or orders
%J Journal de théorie des nombres de Bordeaux
%D 1996
%P 387-396
%V 8
%N 2
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_387_0/
%G en
%F JTNB_1996__8_2_387_0

Huguette Napias. A generalization of the LLL-algorithm over euclidean rings or orders. Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 387-396. https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_387_0/

Bibliographie
Cité par

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

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

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

[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

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