Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Improved methods for calculating vectors of short length in a lattice, including a complexity analysis


Authors: U. Fincke and M. Pohst
Journal: Math. Comp. 44 (1985), 463-471
MSC: Primary 11H50; Secondary 11H55
DOI: https://doi.org/10.1090/S0025-5718-1985-0777278-8
MathSciNet review: 777278
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of $ {{\mathbf{Z}}^m}$ in a suitable box. However, it suffices to consider those $ {\mathbf{x}} \in {{\mathbf{Z}}^m}$ which lie in a suitable ellipsoid having a much smaller volume than the box. We show in this paper that searching through that ellipsoid is in many cases much more efficient. If combined with an appropriate reduction procedure our method allows to do computations in lattices of much higher dimensions. Several randomly constructed numerical examples illustrate the superiority of our new method over the known ones.


References [Enhancements On Off] (What's this?)

  • [1] U. Dieter, "How to calculate shortest vectors in a lattice," Math. Comp., v. 29, 1975, pp. 827-833. MR 0379386 (52:291)
  • [2] U. Fincke & M. Pohst, "Some applications of a Cholesky-type method in algebraic number theory." (To appear.)
  • [3] U. Fincke & M. Pohst, On Reduction Algorithms in Non Linear Integer Mathematical Programming, DGOR-Operations Research Proceedings 83, Springer-Verlag, Berlin and New York, 1983, pp. 289-295. MR 856594
  • [4] D. E. Knuth, The Art of Computer Programming, Vol. II, 2nd ed., Addison-Wesley, Reading, Mass., 1981, pp. 95-97. MR 0378456 (51:14624)
  • [5] A. K. Lenstra, H. W. Lenstra, Jr. & L. Lovasz, "Factoring polynomials with rational coefficients," Math. Ann., v. 261, 1982, pp. 515-534. MR 682664 (84a:12002)
  • [6] A. Odlyzko, "Cryptoanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature system." Preprint, 1983.
  • [7] M. Pohst, "On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications," ACM SIGSAM Bull., v. 15, 1981, pp. 37-44.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11H50, 11H55

Retrieve articles in all journals with MSC: 11H50, 11H55


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1985-0777278-8
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society