scientific article; zbMATH DE number 3972987
[For the entire collection see Zbl 0592.00028.] This expository paper describes the basis reduction algorithm of \textit{A. K. Lenstra}, \textit{H. W. Lenstra} jun. and \textit{L. Lovász} [Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] and its application to the problem of finding a shortest nonzero vector in a lattice. After reviewing the basic facts about lattices, the classical algorithm for finding the shortest nonzero vector in a two-dimensional lattice is explained. The general algorithm is given in terms of the two-dimensional one. Its direct application yields a \(O(\exp (n^ 3))\) algorithm for the computation of a shortest vector in an \(n\)-dimensional lattice. An improvement of this algorithm due to the author has complexity \(n^{o(n)}\). Finally, various applications and open problems are mentioned.
- Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
- A hierarchy of polynomial time lattice basis reduction algorithms
- Simultaneous reduction of a lattice basis and its reciprocal basis
- An algorithm for finding a shortest vector in a two-dimensional modular lattice
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Finding a shortest vector in a two-dimensional lattice modulo m
- Short vectors of planar lattices via continued fractions
- Shortest vector from lattice sieving: a few dimensions for free
- Minimal condition for shortest vectors in lattices of low dimension
- Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem
- Long shortest vectors in low dimensional lattices
- The shortest vector problem and tame kernels of cyclotomic fields
- New orthogonality criterion for shortest vector of lattices and its applications
- Note on shortest and nearest lattice vectors
- Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
- Lattice Reduction Algorithms: Theory and Practice
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- scientific article; zbMATH DE number 3870586 (Why is no real title available?)
- Finding short lattice vectors within Mordell's inequality
- The worst-case behavior of Schnorr's algorithm approximating the shortest nonzero vector in a lattice
- scientific article; zbMATH DE number 5532109 (Why is no real title available?)
- scientific article; zbMATH DE number 3908520 (Why is no real title available?)
- scientific article; zbMATH DE number 3977090 (Why is no real title available?)
- scientific article; zbMATH DE number 3979162 (Why is no real title available?)
- scientific article; zbMATH DE number 3989452 (Why is no real title available?)
- Randomized algorithms in number theory
- Evaluation of linear relations between vectors of a lattice in Euclidean space
- Gauss' algorithm revisited
- scientific article; zbMATH DE number 1256681 (Why is no real title available?)
- Lattice reduction
- scientific article; zbMATH DE number 1313325 (Why is no real title available?)
- scientific article; zbMATH DE number 1998536 (Why is no real title available?)
- A 3-dimensional lattice reduction algorithm
- A parametric version of LLL and some consequences: parametric shortest and closest vector problems
- Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors
- A sieve algorithm for the shortest lattice vector problem
- Selected applications of LLL in number theory
- Computing a lattice basis from a system of generating vectors
- Faster exponential time algorithms for the shortest vector problem
- Reductions between short vector problems and simultaneous approximation
- On the unique shortest lattice vector problem
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3739233)