Abstract
Let L be a k-dimensional lattice in IRm with basis B = (b 1,...,b k). Let A = (a 1,...,a k) be a rational approximation to B. Assume that A has rank k and a lattice basis reduction algorithm applied to the columns of A yields a transformation T = (t 1,...,t k) ε GL(k, ℤ) such that A t i ≤ s i λ i (L(A)) where L(A) is the lattice generated by the columns of A, λ i (L(A)) is the i-th successive minimum of that lattice and s i ≥ 1, 1 ≤ i ≤ k. For c > 0 we determine which precision of A is necessary to guarantee that B t i ≤ (1+c)s i λ i (L), 1 ≤ i ≤ k. As an application it is shown that Korkine-Zolotaref-reduction and LLL-reduction of a non integer lattice basis can be effected almost as fast as such reductions of an integer lattice basis.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Buchmann, M. Pohst: Computing a lattice basis from a system of generating vectors, Proceedings EUROCAL 87, Springer Lecture Notes in Computer Science 378, 54–63, 1989.
J. Buchmann, V. Kessler: Computing a reduced lattice basis from a generating system, preprint, 1993.
A.K. Lenstra, H.W. Lenstra Jr., L. Lovász: Factoring polynomials with rational coefficients, Math. Ann. 261, 515–534, 1982.
M. Grötschel, L. Lovász, A. Schrijver: Geometric algorithms and combinatorial optimization, Springer-Verlag Berlin Heidelberg, 1988.
J.L. Hafner, K.S. McCurley: Asymptotically fast triangularization of matrices over rings, SIAM J. Computation 20, no. 6, 1068–1083, 1991.
B. Helfrich, Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, Theoretical Computer Science 41, 125–139, 1985.
M. Pohst: A modification of the LLL Reduction Algorithm, J. Symbolic Computation, 4, 123–127, 1987.
J.C. Lagarias, H.W. Lenstra Jr., C.P. Schnorr: Korkine-Zolotarev bases and successive minima of a lattice and its dual lattice, Combinatorica 10, no.4, 333–348, 1990.
B.L. van der Waerden and H. Gross: Studien zur Theorie der Quadratischen Formen, Birkhäuser, Basel, 1968.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buchmann, J. (1994). Reducing lattice bases by means of approximations. In: Adleman, L.M., Huang, MD. (eds) Algorithmic Number Theory. ANTS 1994. Lecture Notes in Computer Science, vol 877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58691-1_54
Download citation
DOI: https://doi.org/10.1007/3-540-58691-1_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58691-3
Online ISBN: 978-3-540-49044-9
eBook Packages: Springer Book Archive