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

Huguette Napias

Journal de théorie des nombres de Bordeaux (1996)

  • Volume: 8, Issue: 2, page 387-396
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Napias, Huguette. "A generalization of the LLL-algorithm over euclidean rings or orders." Journal de théorie des nombres de Bordeaux 8.2 (1996): 387-396. <http://eudml.org/doc/247839>.

@article{Napias1996,
abstract = {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.},
author = {Napias, Huguette},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {lattices over orders; Euclidean rings; maximal orders of imaginary quadratic fields; orders of a quaternion algebra; LLL-algorithm; lattice basis reduction},
language = {eng},
number = {2},
pages = {387-396},
publisher = {Université Bordeaux I},
title = {A generalization of the LLL-algorithm over euclidean rings or orders},
url = {http://eudml.org/doc/247839},
volume = {8},
year = {1996},
}

TY - JOUR
AU - Napias, Huguette
TI - A generalization of the LLL-algorithm over euclidean rings or orders
JO - Journal de théorie des nombres de Bordeaux
PY - 1996
PB - Université Bordeaux I
VL - 8
IS - 2
SP - 387
EP - 396
AB - 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.
LA - eng
KW - lattices over orders; Euclidean rings; maximal orders of imaginary quadratic fields; orders of a quaternion algebra; LLL-algorithm; lattice basis reduction
UR - http://eudml.org/doc/247839
ER -

References

top
  1. [1] Ch. Bachoc, Voisinage au sens de Kneser pour les réseaux quaternioniens, Comm. Math. Helvet.70 (1995), 350-374. Zbl0843.11022MR1340098
  2. [2] Ch. Bachoc, Applications of coding theory to the construction of modular lattices, to appear. Zbl0876.94053MR1439633
  3. [3] Ch. Batut, D. Bernardi, H. Cohen and M. Olivier, User's Guide to PARI-GP. 
  4. [4] J.W.S. Cassels, Rational Quadratic Forms, Academic Press, London, 1978. Zbl0395.10029MR522835
  5. [5] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Graduate Texts in Mathematics, n°138, 1995. Zbl0786.11071MR1228206
  6. [6] C. Fieker and M.E. Pohst, On lattices over number fields, preprint. MR1446505
  7. [7] G.H. Hardy and E.M. Wright, An introduction to the theory of numbers (1954), Oxford university press. Zbl0058.03301MR67125
  8. [8] F. Lemmermeyer, The Euclidean algorithm in algebraic number fields, preprint. Zbl0843.11046MR1362867
  9. [9] A.K. Lenstra, H.W. Lenstra, Jr and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann.261 (1982), 515-534. Zbl0488.12001MR682664
  10. [10] J. Martinet, Les réseaux parfaits des espaces euclidiens, to appear. MR1434803
  11. [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. Zbl0829.11035MR1345179
  12. [12] H. Napias, Etude expérimentale et algorithmique de réseaux euclidiens, Thèse, Univ. Bordeaux I (1996). 
  13. [13] G. Nebe, W. Plesken, Memoirs A.M.S., vol. 116, number 556, pp. 1-144. MR1265024
  14. [14] M. Pohst, A modification of the LLL-algorithm, J. Symb. Comp.4 (1987), 123-128. Zbl0629.10001MR908420

NotesEmbed ?

top

You must be logged in to post comments.