Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. (English) Zbl 0601.68034

In 1983, Kannan presented an algorithm to construct a Hermite reduced basis of a lattice \(L=\sum^{n}_{i=1}b_ i {\mathbb{Z}}\) in \({\mathbb{R}}^ d\) \((b_ i\) linear independent vectors of \({\mathbb{R}}^ d)\). In this paper, which is an outgrow of the author’s Ph. D. thesis under the guidance of C. P. Schnorr, an idea of C. P. Schnorr is used to reduce the complexity from \((4n)^{1.5n+O(1)}\) to \(n^{0.5n+O(n)}\). Using the fact that a basis \((b_ 1,...,b_{i-1})\) is Hermite reduced if \((b_ 1,...,b_ n)\) is, the author also improves Kannan’s recursion algorithm to solve the closest lattice point problem.
Reviewer: A.Bachem


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


[1] Babai, L., On lovász’ lattice reduction and the nearest lattice point problem, (), 13-20 · Zbl 0593.68030
[2] Cassels, J.W.S., An introduction to the geometry of numbers, (1959), Springer Berlin/Heidelberg · Zbl 0086.26203
[3] Cassels, J.W.S., Rational quadratic forms, (1978), Academic Press New York · Zbl 0395.10029
[4] Gauss, C.F., Disquisitiones arithmeticae, (1889), Springer Berlin, (German translation) · JFM 21.0166.04
[5] Helfrich, B., Reduktionsalgorithmen für gitterbasen, ()
[6] Hermite, C.H., Deuxième lettre à Jacobi, (), 122-135
[7] Kannan, R.; Lenstra, A.K.; Lovász, L., Polynomial factorisation and nonrandomness of bits of algebraic and some transcendental numbers, () · Zbl 0654.12001
[8] Kannan, R., Improved algorithms for integer programming and related problems, (), 193-206
[9] Kannan, R., Lattices, basis reduction and the shortest vector problem, () · Zbl 0603.12001
[10] Korkine, A.; Zolotareff, G., Sur LES formes quadratiques, Math. ann., 6, 366-389, (1873) · JFM 05.0109.01
[11] 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
[12] Lagarias, J.C., Computational complexity of simultaneous Diophantine approximation problems, (), 32-39 · Zbl 0563.10025
[13] Lagarias, J.C.; Odlyzko, A.M., Solving low density subset sum problems, (), 1-10 · Zbl 0632.94007
[14] Lekkerkerker, C.G., Geometry of numbers, (1969), North-Holland Amsterdam · Zbl 0198.38002
[15] Lenstra, A.K.; Lenstra, H.W.; Lovász, L., Factoring polynomials with rational coefficients, Math. ann., 261, 513-534, (1982) · Zbl 0488.12001
[16] Minkowski, H., Über die positiven quadratischen formen und über kettenbruchähnliche algorithmen, J. reine angew. math., 107, 278-297, (1891) · JFM 23.0212.01
[17] Schnorr, C.P., A hierarchy of polynomial time basis reduction algorithms, () · Zbl 0633.10002
[18] Schönhage, A., Factorization of univariate integer polynomials by Diophantine approximation and by an improved basis reduction algorithm, (1983), Preprint, Tübingen
[19] van Emde Boas, P., Another NP-complete partition problem and the complexity of computing short vectors in a lattice, () · Zbl 0329.68045
[20] van der Waerden, B.L.; Gross, H., Studien zur theorie der quadratischen formen, (1968), Birkhäuser Basel · Zbl 0185.11002
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.