How to calculate shortest vectors in a lattice
Math. Comp. 29 (1975), 827-833
Primary 10E20; Secondary 65K05
Full-text PDF Free Access
Similar Articles |
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.
R. Coveyou and R.
D. Macpherson, Fourier analysis of uniform random number
generators, J. Assoc. Comput. Mach. 14 (1967),
100–119. MR 0221727
U. DIETER & J. H. AHRENS, Pseudo-Random Numbers, Preliminary version in preprint (430 pages), Wiley, New York. (To appear.)
E. Knuth, The art of computer programming. Vol. 2: Seminumerical
algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don
Mills, Ont, 1969. MR 0286318
Marsaglia, Random numbers fall mainly in the planes, Proc.
Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 0235695
H. MINKOWSKI, Gesammelte Abhandlungen, especially Vol. I, pp. 243-260, Vol. II, pp. 3-42, Teubner-Verlag, Leipzig, 1911.
- R. R. COVEYOU & R. D. MACPHERSON, "Fourier analysis of uniform random number generators," J. Assoc. Comput. Mach., v. 14, 1967, pp. 100-119. MR 36 #4779. MR 0221727 (36:4779)
- U. DIETER & J. H. AHRENS, Pseudo-Random Numbers, Preliminary version in preprint (430 pages), Wiley, New York. (To appear.)
- D. E. KNUTH, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
- G. MARSAGLIA, "Randon numbers fall mainly in the planes," Proc. Nat. Acad. Sci. U.S.A., v. 61, 1968, pp. 25-28. MR 18, 947. MR 0235695 (38:3998)
- H. MINKOWSKI, Gesammelte Abhandlungen, especially Vol. I, pp. 243-260, Vol. II, pp. 3-42, Teubner-Verlag, Leipzig, 1911.
Retrieve articles in Mathematics of Computation
Retrieve articles in all journals
Geometry of numbers,
minima of forms,
random number generation
© Copyright 1975
American Mathematical Society