Abstract
Given a latticeL we are looking for a basisB=[b 1, ...b n ] ofL with the property that bothB and the associated basisB *=[b *1 , ...,b * n ] of the reciprocal latticeL * consist of short vectors. For any such basisB with reciprocal basisB * let\(S(B) = \mathop {\max }\limits_{1 \leqslant i \leqslant n} (|b_i | \cdot |b_i^ * |)\). Håstad and Lagarias [7] show that each latticeL of full rank has a basisB withS(B)≤exp(c 1·n 1/3) for a constantc 1 independent ofn. We improve this upper bound toS(B)≤exp(c 2·(lnn)2) withc 2 independent ofn.
We will also introduce some new kinds of lattice basis reduction and an algorithm to compute one of them. The new algorithm proceeds by reducing the quantity\(\sum\limits_{i = 1}^n {|b|^2 } \cdot |b_i^ * |^2 \). In combination with an exhaustive search procedure, one obtains an algorithm to compute the shortest vector and a Korkine-Zolotarev reduced basis of a lattice that is efficient in practice for dimension up to 30.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. H. Conway, andN. J. A. Sloane:Sphere packings, lattices and groups, Springer Verlag, New York, 1988.
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, andC. P. Schnorr: An improved low-density subset sum algorithm, to appear inComputational Complexity.
U. Dieter: How to compute the shortest vector in a lattice,Math. Comp. 29 (1975), 827–833.
M. Euchner, andC. P. Schnorr: Lattice basis reduction: improved practical algorithms and solving subset sum problems,Proceedings of Fundamentals of Computation Theory, FTC '91, Ed. L. Budach, Springer LNCS529 (1991) 68–85.
P. M. Gruber, andJ. Lekkerkerker:Geometry of numbers, North Holland, Amsterdam, 1987.
Johan Håstad, B. Just, J. C. Lagarias, andC. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers,SIAM J. Comput. 18 (1989), 859–881.
Johan Håstad, andJ. C. Lagarias: Simultaneously good bases of a lattice and its reciprocal lattice,Math. Ann. 287 (1990), 163–174.
R. Kannan: Improved algorithms on integer programming and related lattice problems,Proc. 15th Annual ACM Symp. on Theory of Computing (1983), 293–206.
D. E. Knuth:The art of computer programming, Vol. 2: Seminumerical algorithms, 2nd edition, Addison-Wesley, 1981.
A. Korkine, andG. Zolotarev: Sur les formes quadratiques,Math. Ann. 6 (1873), 366–389.
J. C. Lagarias, H. W. Lenstra, Jr., andC. P. Schnorr: Korkine Zolotarev bases and successive minima of a lattice and its reciprocal,Combinatorica 10 (1990), 333–348.
J. C. Lagarias, andA. M. Odlyzko: Solving low-density subset sum problems,J. Assoc. Comp. Mach. 32 (1985), 229–246.
B. A. LaMacchia: Basis reduction algorithms and subset sum problems. Thesis for the degree of Master of Science, Department of Electrical engineering and Computer Science, Massachusetts Institute mof Technology, May 1991.
A. K. Lenstra, H. W. Lenstra, Jr., andL. Lovász: Factoring polynomials with rational coefficients,Math. Ann. 261 (1982), 515–534.
H. W. Lenstra, Jr.: Integer programming with a fixed number of variables,Math. Oper. Res. 8 (1983), 538–548.
C. P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms,Theor. Comp. Sci. 53 (1987), 201–227.
C. P. Schnorr: A more efficient algorithm for lattice basis reduction,J. Algorithms 9 (1988), 47–62.
C. P. Schnorr: Factoring integers and computing discrete logarithms via diophantine approximation,Proceedings of Eurocrypt '91, Brighton, May 1991, to appear in Springer LNCS.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Seysen, M. Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica 13, 363–376 (1993). https://doi.org/10.1007/BF01202355
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01202355