A hierarchy of polynomial time lattice basis reduction algorithms. (English) Zbl 0642.10030

We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine-Zolotareff reduction. Let \(\lambda\) (L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for \(k\in {\mathbb{N}}\) finds a nonzero lattice vector b so that \(| b|^ 2\leq (6k^ 2)^{n/k}\lambda (L)^ 2.\) This algorithm uses \(O(n^ 2(\sqrt{k^{k+o(k)}}+n^ 2)\log B\) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors \(b_ 1,...,b_ n\in {\mathbb{Z}}^ n\) are integral and have the length bound B. This algorithm successively applies Korkine-Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan’s algorithm for Korkine-Zolotareff reduction.


11H55 Quadratic forms (reduction theory, extreme forms, etc.)
68Q25 Analysis of algorithms and problem complexity
11H06 Lattices and convex bodies (number-theoretic aspects)
Full Text: DOI


[1] Cassels, J. W.S., An introduction to the geometry of numbers, (1971), Springer Berlin · Zbl 0209.34401
[2] van Emde Boas, P., Another NP-complete problem and the complexity of computing short vectors in a lattice, (Tech. Rept., (1981), University Amsterdam), No. 81-04
[3] Frank, A.; Tardos, E., An application of simultaneous approximation in combinatorial optimization, (Report, (1985), Universität Bonn)
[4] Gauss, C. F., Disquisitiones arithmeticae, (1889), Springer Berlin, (reprints: Chelsea, New York, 1981) · JFM 21.0166.04
[5] Hastad, J.; Just, B.; Lagarias, J. C.; Schnorr, C. P., Polynomial time algorithms for finding integer relations among real numbers, (Proc. 3rd STACS 86, Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 210, (1985), Springer Berlin), 105-118
[6] Helfrich, B., Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, Theoret. Comput. Sci., 41, 125-139, (1985) · Zbl 0601.68034
[7] Hermite, Ch., Second letter to Jacobi, Crelle Journal, 40, 279-290, (1850), (in French)
[8] Kannan, R., Improved algorithms for integer programming and related lattice problems, Proc. 15th Ann. ACM Symp. on Theory of Computing, 193-206, (1983)
[9] Korkine, A.; Zolotareff, G., Sur LES forms quadratiques, Math. Annalen, 6, 366-389, (1873) · JFM 05.0109.01
[10] Lagarias, J. C., Worst case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms, 1, 142-186, (1980) · Zbl 0473.68030
[11] J. C. Lagarias, H.W. Lenstra, Jr. and C.P. Schnorr, Korkine-Zolotareff bases and successive minima of a lattice and its reciprocal lattice, Tech. Rept., MSRI 07718-86, Mathematical Sciences Research Institute, Berkeley. · Zbl 0723.11029
[12] Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548, (1983) · Zbl 0524.90067
[13] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Annalen, 261, 515-534, (1982) · Zbl 0488.12001
[14] L. Lovász, An algorithmic theory of numbers, graphs and convexity, Tech. Rept., Universität Bonn.
[15] Minkowski, H., Über die positiven quadratischen formen und über kettenbruchähnliche algorithmen, Crelles Journal für die reine und angewandte mathematik, 107, 278-297, (1891) · JFM 23.0212.01
[16] Odlyzko, A. M.; te Riele, H., Disproof of the mertens conjecture, Journal für die reine und angewandte Mathematik, 357, 138-160, (1985) · Zbl 0544.10047
[17] Schnorr, C. P., A more efficient algorithm for lattice basis reduction (extended abstract), (Proc. 13th Coll. on Automata, Languages and Programming, Rennes 1986, Lecture Notes in Computer Science, 226, (1986), Springer Berlin), 359-369, complete version to appear in J. Algorithms (December 1987) · Zbl 0595.68038
[18] Schönhage, A., Factorization of univariate integer polynomials by Diophantine approximation and by an improved basis reduction algorithm, (Proc. 11th Coll. on Automata, Languages and Programming, Antwerpen 1984, Lecture Notes in Computer Science, 172, (1984), Springer Berlin) · Zbl 0569.68030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.