Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

How to calculate shortest vectors in a lattice


Author: U. Dieter
Journal: Math. Comp. 29 (1975), 827-833
MSC: Primary 10E20; Secondary 65K05
MathSciNet review: 0379386
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A method for calculating vectors of smallest norm in a given lattice is outlined. The norm is defined by means of a convex, compact, and symmetric subset of the given space. The main tool is the systematic use of the dual lattice. The method generalizes an algorithm presented by Coveyou and MacPherson, and improved by Knuth, for the determination of vectors of smallest Euclidean norm.


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

  • [1] R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 0221727 (36 #4779)
  • [2] U. DIETER & J. H. AHRENS, Pseudo-Random Numbers, Preliminary version in preprint (430 pages), Wiley, New York. (To appear.)
  • [3] Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR 0286318 (44 #3531)
  • [4] George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 0235695 (38 #3998)
  • [5] H. MINKOWSKI, Gesammelte Abhandlungen, especially Vol. I, pp. 243-260, Vol. II, pp. 3-42, Teubner-Verlag, Leipzig, 1911.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10E20, 65K05

Retrieve articles in all journals with MSC: 10E20, 65K05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1975-0379386-6
PII: S 0025-5718(1975)0379386-6
Keywords: Geometry of numbers, lattice theory, minima of forms, random number generation
Article copyright: © Copyright 1975 American Mathematical Society